T1
做法 1：莫队。（考虑一个数的出现次数变化时的影响。）应该可以直接做，似乎也可以正难则反（见做法 2）。
做法 2：[扫描线]（？）。按询问右端点排序。记一下每个位置前面最近的和它权值相同的位置。一种是直接做，分讨。一种是正难则反：算前缀和；算出现次数为 \(2\) 的数的贡献之和，减去这部分贡献。
如果强制在线似乎可以树套树，与做法 2 类似；似乎也可以在线莫队（用前缀和来优化空间）。
T2
路径异或和 -> 算 到根的异或和。注意要额外亦或上 LCA 的权值。
两个数亦或起来最大 -> 01-Trie 启动！
路径问题。有根树就先不考虑点分治了。于是用 启发式合并 或 dsu on tree。
可能也可以想想能不能用 [有根树点分治]（我自己随便这么称呼的）做。
（非常需要注意！因为[这个错已经是我第二次犯了]（？？？））注意：要处理完一棵轻子树的贡献后再把这棵轻子树里的所有结点插入到 01-Trie 里，而不能边算贡献边插入。因为一棵子树里的点不能互相一起造成贡献。
T3
要写一种数据结构，支持插入和求第 k 小值，但是 k 是 + 1 这样变化的（k 的变化很小）。
我写的 FHQ-Treap 被卡了呜呜呜。上面这种问题可以用[对顶堆]（？）做（本题正解）。
注意：添加元素的时候不能无脑加到一个堆里，而应该判断它是否比[小堆]（我自己随便这么称呼的）（大根）的最大值小，如果是就丢进小堆，否则丢进大堆。
注意：看一个堆的堆顶时要考虑这个堆是不是空的。（如果时空的好像会 [RE]（？？？））
教训
-
T2、T3 里的三条注意（加粗了）。
-
T3 那种题，不要忘了[对顶堆]（？）。
经验
-
考虑开不开 long long。
-
算空间。（可以算相当于多少个 int）
2024.9.16
标签：16,2024.9,T3,贡献,注意,做法,DS From： https://www.cnblogs.com/huangkxQwQ/p/18416549