题解：CF840E In a Trap

forest114514 · 2025-06-24 21:20:59 · 题解

设 V=\log_2(n)。

我们对于每个点上方 2^{V-B} 个数拿出来，此时最低 B 位就依次变成 x\oplus i 是个固定的值了，中间 2^{B} 位需要考虑每一个的答案。（>2^V 的位置显然我们只用保留最大的数，其他都扔了，后面就认为这个不存在了，其实也就是说明和值域没关系了。）

然后再对于中间 B 位一样的数，显然只用保留前 V-B 位最大的那个，于是现在所有的数中我们只用找到 0\sim 2^{B}-1 在剩下的 0\sim 2^{B}-1 的一个子集中找一个数使得异或起来最大。

用 trie 树是 O(nB2^B) 的，需要优化，注意当前在 trie 树上的最优取值只会是一个若干位没确定，若干位确定的数，遇到两个儿子都有的时候会把当前位按 01 分裂即确定当前位的取值，最后在叶子节点的时候再枚举没确定的位来确定贡献。

我们没必要在线建 trie，显然 0\sim 2^{B}-1 在 trie 上节点数是 O(2^B)，所以直接整体建出 trie 这样复杂度就是 O(2^B) 了，然后 dfs 的复杂度也是 O(2^B) 的。

这样预处理是 O(n(2^{B}+2^{V-B}))，查询是 O(q(2^{B}+2^{V-B}))，可以平衡到 O((n+q)\sqrt n)。