可持久化数据结构

P4735

转化到区间求 \(\text{xor} \ x\) 后的最大值，用 Trie。那么需要知道区间是否有在 Trie 树某个子树内的节点，用可持久 Trie，或者离线扫右端点并记录左端点时间戳即可。

第二个做法可以不离线，同样使用可持久 Trie，但是求区间时不使用减法，而是只使用插入前 \(r\) 个数的 Trie，通过在每个节点记录该节点子树内所有点的最小值，来判断值域区间内是否有点。

写了第一个。两个做法还有一个没调出来。

凑区间的另一个方法是树状数组那种拆分，不要求信息有可减性，那么每个点会被插进 \(\log\) 个 Trie 中。好像可以动态修改。好像达成了修改的查询的平衡。复杂度多一只 \(\log\)。

P5283

\(i < j\)：直接去掉，让 \(k \gets 2k\)。另一个做法是拆分 \(i\) 的取值区间，初始为 \([1, j-1]\)，每取走一个值分裂一次。或者直接给原做法套可持久化 Trie。本来要求异或 \(k\) 大值，现在要求区间极值。本质都在寻找下一大值。

维护所有可能成为下一个答案的数值，一边扫描一边加新的值进来。

具体而言，维护一个堆，当取出堆顶时，设它由 \(a_u\) 产生，取与 \(a_u\) 异或值最大的小于刚取出的值的数值入堆，它为下一个可能成为答案的数值。（考虑到相等事实上是排名为下一个）复杂度 \(O(k \log n)\)。

需要快速找到排名为下一位的通过 \(a_u\) 产生的数值。

拓展：不依据 \(k\) 的做法。

先快速求出第 \(k\) 大的值。逐位确定之。若现在确定了 \(i\) 位，对于每个 \(a_x\) 找一个 \(b_x\)，使得 \(b_x\) 的深度为 \(i\)，且 \(a_x \ \text{xor} \ b_x\) 的前 \(i\) 位为答案，这样可以确定下一位的方向。找到答案后，需要求所有比答案大的异或值之和。对于每个 \(a_i\)，通过枚举它与最大值第一位不一样处，得到答案最多位于 \(\log\) 棵子树内。而 Trie 的子树是原数组排序后连续一段，拆位做前缀和即可。复杂度 \(O(n \log n \log V)\)。

都是对 \(n\) 个 \(a_i\) 逐位限制操作。

references:

https://www.luogu.com.cn/article/ipa5pxaj

https://www.luogu.com.cn/article/mdn29sxp

P2633

用 \(1 \to u \ + \ 1 \to v \ - \ 2 \cdot 1 \to \text{lca}(u, v)\) 造路径即可。在每个点处维护一棵值域线段树，为了空间需要可持久化。

换非递归 Trie 试试。

如果想带修估计要树剖+树状数组，三只 \(\log\)。看着好蠢，想不到更好的做法。