首先这是一道语文题（233）
翻译题目后，我们可以知道有如下的题意：
考虑建立 trie 树。然而 trie 树维护的是前缀，此题要求后缀。不需要很多麻烦的操作，因为此题答案只和后缀有关，把串反过来就好了。
然后在 trie 树上建一个图，具体地，trie 树上如果一个结尾点位于结尾点的子树，从深度小的向深度大的连边。
然后依照 dfs 序跑一次贪心就好了。
首先 \(O(n^2)\) 的做法比较好想，搞一个并查集就好了。具体地，对于 \(l1 \sim r1\) 中每一个位置向 \(l2 \sim r2\) 对应的位置建立附属关系，最后 \(O(n)\) 查询得解。
然而只能获得部分分，因此考虑优化。
注意到只有一次询问，我们能否将修改和查询都降至 \(\log\) 级别呢？
这时，倍增的思想就呼之欲出了。我们将并查集分为 \(\log n\) 层，以位置 \(i\) 起始的第 \(j\) 层并查集维护了 \(i \sim i + 2^j - 1\) 的信息。在修改的时候，把 \(l \sim r\) 分为若干个 \(2\) 的次幂的块，在对应的并查集层级维护信息。
查询也是 \(\log\) 级别。我们只需要依次分裂并查集，对于以位置 \(i\) 起始的第 \(j\) 层并查集，我们可以将其分裂为以位置 \(i\) 起始的第 \(j-1\) 层并查集和以位置 \(i+2^(j-1)\) 起始的第 \(j-1\) 层并查集，直至分裂到只剩第 \(0\) 层，这时直接查询即可。
假设你查询的答案为 \(x\)，注意答案并不是 \(10^x\)，而是 \(9 \times 10^{x-1}\)。
可持久化 01-trie。
考前只学过主席树，没学过这玩意儿。但是类比上来还是很容易的，但是由于我太菜，在其他地方又栽了个跟头……
回到正题。考虑如果是询问 \(a_1 \oplus a_2 \oplus ... \oplus a_p \oplus x\) 的最大值 ，令 \(b_i = a_1 \oplus a_2 \oplus ... \oplus a_i\)，则相当于在 \(l \sim r\) 中找到 \(p\) 使得 \(b_p \oplus x\) 最大，这是可持久化 Trie 树的裸题。
但是现在是询问 \(a_p \oplus a_{p+1} \oplus ... \oplus a_n \oplus x\) 。 考虑对 \(a_1 \oplus a_2 \oplus ... \oplus a_{p-1} \oplus x\) 异或上 \(b_n = a_1 \oplus ... \oplus a_n\) 则为所求式子 。
于是就很简单了，维护前缀异或和和前缀异或和的可持久化 01-trie，查询时直接令 \(q=b_n \oplus x\)，让 \(q\) 在 \(l-1\) 和 \(r-1\) 之间的 01-trie 跑贪心就可以了。
原文：https://www.cnblogs.com/sqrtyz/p/13418651.html