P3293 [SCOI2016] 美味
前置知识：0-1 Trie 求最大（小）异或值。这个应该所有人都会了，但是这里怕你们说我不负责讲一讲。0-1 Trie 把存进去的每个整数由高位向低位存储二进制值，前面没有就补齐 0。当需要在 Trie 存储的数中找到一个使它与给定数的异或值最大时，从高到低位遍历给定数并从根节点遍历 Trie. 如果当前位为 0 就寻找 Trie 的当前节点有没有值为 1 的儿子，否则查找有没有值为 0 的儿子（与给定数正好相反）。如果有就递归与原数相反的位，否则就只能递归另一个位了。这个贪心确保了最高位的值。
此题只是加了一个 xix_ixi . 怎么做呢？依旧遍历 bib_ibi 的位。如果是 1，我们希望能找到一个此位为 0 的 aia_iai . 如图：
我们要找最小 a 和最大 a 之间有没有值。注意到最小 a 正好就是当前的 ans, 最大值可以算出是 ans+2i−1ans+2^i-1ans+2i−1 ，其中 i 是当前位到最右端的距离。
于是我们只需要求在两个区间 [l,r][l,r][l,r] 和 [ans,ans+2i−1][ans,ans+2^i-1][ans,ans+2i−1] 的约束条件下有没有值即可。如果 b 的当前位是 0，我们也可以计算出对应的左右端点，具体看代码。有两个区间的约束条件，考虑主席树。下面的主席树使用了一种类似 0-1 Trie 的存储方法，但其实和主席树的普通写法是一样的。我原先是求具体有多少个值再判断，但是这个玩意似乎可以直接返回 bool 值然后通过短路的性质优化。于是我就从 2.50s 加速到了 1.80s.
Code:Code:Code:
