可持久化线段树
P2839 middle
好题。首先有关于中位数的 trick，假设当前的数为 \(x\)，我们把大于等于 \(x\) 的数标为 \(1\)，小于 \(x\) 的标为 \(-1\)。在本题中，0-index 下取整等价于 1-index 上取整，所以只要一段区间的和大于等于 \(0\)，那么中位数一定大于等于 \(x\)。通过反证容易证明。
这是可以二分的，但直接 check 并不容易。先不考虑时空限制，每次对于二分出的中位数 mid，我们按照上面的方法建出线段树，线段树维护区间和，区间最大前缀和，最大后缀和。记作 \(sum, pre, suf\)。
满足条件的最大和即为 \(sum_{b + 1, c - 1} + suf_{a, b} + pre_{c,d}\) 。但这样搞我们需要对每个 mid 建立线段树，时空复杂度过高。
考虑 mid 从小到大增长，原序列中每一个数只会被扫过一次，这启发我们对序列建立可持久化线段树，版本 \(i\) 维护当前数为 \(i\) 时的 \(-1, 1\) 序列，然后就做完了。
P4899 werewolf 狼人
经典套路学习，重构树配合可持久化。
首先需要重构树是显然的，建出两颗重构树，点权分别表示经过的编号的最小值和最大值，然后倍增出起点和终点能到的祖先，它的子树内都可以到达。
由于子树内 dfs 序连续，问题转化成给定两个排列 \(A, B\)，区间 \([l1, r1], [l2, r2]\)，求 \(A_{l1, r1}\) 与 \(B_{l2, r2}\) 是否有交。考虑把 \(A\) 中的点映射到 \(B\) 的位置上， \(pos_i\) 表示 \(A_i\) 在 \(B\) 中的位置。最后查询 \([l1, r1]\) 版本中 \([l2, r2]\) 区间范围内是否有值即可。
我都看不懂我在写啥了，留个代码。
rep(i, 1, maxn) pos[i] = tr2.dfn[tr1.rnk[i]];
rep(i, 1, maxn) tree.insert(rt[i - 1], rt[i], 1, maxn, pos[i], tr1.rnk[i] <= n);
注意交点只能在原始点上，只有是原始点才真的加 \(1\)。
CF543E Listening to Music
不强制在线是唐诗题，按权值从小到大加入，每次做个区间加，查询求个区间最小值即可。
强制在线，套个主席树，每次询问二分一下位置，做完了。
64 MB，真恶心，疯狂卡空间，使用神秘 bit field，极限卡过。
可持久化平衡树
只过了板子，两道 Ynoi 不会捏。
可持久化 Trie
P5283 十二省联考 2019 异或粽子
首先肯定前缀和一下，然后找前 \(k\) 大有通用的搞法，开一个大根堆维护每一个右端点能匹配到的最大值，取出来一个换成次大值，以此类推。
所以问题关键变成快速求出某个右端点能匹配的第 \(k\) 大值，这个显然可以上持久化 Trie ，然后插入时顺手维护一下 siz，每次进去查一下，就做完了。
这是因为 \(k\) 比较小，所以可以这样比较方便地做。
CF241B Friends
上一题严格加强版，\(n \le 5 \times 10 ^ 4, k \le \dfrac{n(n - 1)}{2}\) ，显然枚举出来不现实，我们需要复杂度与 \(k\) 无关的算法。考虑二分出第 \(k\) 大。
如何 check 呢？我们需要对于每一个 \(a_i\) 找出与它异或大于等于 \(mid\) 的数有多少个，这个可以 Trie 维护一下 siz，往下走顺便计算答案就 ok 了。
同时，我们还要计算和，需要同时维护一个 \(val_{x, i}\) 表示在 \(x\) 子树内第 \(i\) 位是 \(1\) 的数有多少个，这样可以同时计算出和。
计算和的部分要注意，直接边走边算会变成三只 \(\log\) ，考虑记录中途走过的点的编号，最后合起来一起计算 ，这样是两只 \(\log\)。
显然如果严格按照要求来需要可持久化，可持久化会很卡空间，常数还贼大。这种题可以考虑直接不管不能重复计算的限制，转为求前 \(2m\) 大的异或和，最后除以 \(2\) 就行了。
复杂度 \(O(n \log^2 \omega)\)。
P5795 THUSC2015 异或运算
怎么全是第 \(k\) 大。
看起来很板，实际上也很板的题。一眼丁真，\(n\) 这么小，\(m\) 又巨大，直接对 \(m\) 建可持久化 Trie，每次暴力二分一下，这不直接做完了？
喜获 90 pts，发现复杂度是 \(O(qn \log^2 \omega)\) 的，极限数据 \(4.5 \times 10 ^ 8\)，2s 跑不过。
来个一只 \(\log\) 的二分，即每次从上往下贪心的时候，假设这一位填 \(1\)，直接 \(O(n)\) 扫一遍计算现在数还够不够，根据结果移动即可。就是上面异或粽子一个数变成多个数而已。
原来这么简单，之前写的两只 \(\log\) 更唐了。
P4592 TJOI2018 异或
太水了，直接口胡。
可持久化维护两个 Trie，一个 dfs 序，一个根到当前节点。 求个 LCA 就做完了。
可持久化并查集
可持久化可并堆
不学了，感觉用不上，写树套树去了。