HDU 6955. Xor Sum
题目链接：HDU 6955. Xor Sum
题意：
给一个长度为\(n\)的一个整数序列\({a_n}\)，寻找最短的，满足异或和大于等于\(k\)的连续子序列。输出子序列的左端点和右端点，若有多个最短长度的连续子序列，输出位置靠前的。不存在满足条件的连续子序列，输出\(-1\)。
输入：
第\(1\)行一个整数\(t(t\leq100)\)，代表测试样例个数。
对于每一个样例：
第\(1\)行，有两个整数\(n(1\leq n\leq 10^5),k(0\leq k<2^{30})\)，分别代表整数序列的长度和题意中的\(k\)。
第\(2\)行，有\(n\)个整数\(a_1,a_2,...,a_n(0\leq a_i<2^{30})\)，代表这个整数序列。
输出：
对于每一个样例：
若存在这样的连续子序列，输出连续子序列的左端点和右端点。
若有多个最短长度的连续子序列，输出位置靠前的那一个。
若不存在满足条件的连续子序列，输出\(-1\)。
分析：
首先，异或满足这样的性质：
这使得我们可以使用前缀异或和。
设\(sum[1...i]=S_i\)，特别地，定义\(S_0=0\)，于是有
从而可以将原问题转化为，在\(S_0,S_1,...,S_n\)中寻找一对在序列中距离最短的\(S_i,S_j(i<j)\)，满足\(S_i\oplus S_j\geq k\)，最终答案即为\([i+1,j]\)（\(i+1\)是左端点，\(j\)是右端点）
最暴力的想法为：使用二层循环，第一层从\(1\)到\(n\)枚举距离\(d\)，第二层枚举\(i(0\leq i\leq n+1-d)\)，判断\(S_i\oplus S_{i+d-1}\geq k\)是否成立，成立则说明答案已经找到，跳出循环，不成立则继续循环。
暴力做法时间复杂度为\(O(n^2)\)，会超时，所以需要优化。不妨考虑枚举右侧端点\(i\)，试试看能否在区间\([0,i-1]\)上快速找到离\(i\)最近的\(j\)，使得\(S_j\oplus S_i\geq k\)。
既然是异或问题，一定和二进制相关，而题目给出的范围是\(0\leq a_i<2^{30}\)，所以\(S_i\)也在这个范围中，说明\(S_i\)可以用\(30\)位二进制表示，于是\(S_i\)可以看成长度为\(30\)的"01"字符串。
故而可以考虑在枚举\(i\)的时候，动态地维护一个包含\(S_0,S_1,...,S_{i-1}\)的"01"字典树，其中深度小的节点存储高位，深度大的节点存储低位。字典树的每个节点附加存储着这个节点所表示的前缀（从高位开始的"01"串）最后一次在数列\(S_0,S_1,...,S_{i-1}\)中出现的位置，没出现过位置就记成\(-1\)。
然后让\(S_i\)和字典树中的串进行带剪枝的逐位异或：
为了方便描述，记\(S_i\)中从高位到低位数起第\(j\)位（以下简称“第\(j\)位”）为\(S_{ij}\)，\(k\)中第\(j\)位是\(k_j\)。
假设目前正在考虑第\(j\)位的情况，即到达了字典树的第\(j-1\)层（根节点为空前缀，把它当成第\(0\)层），考虑往哪个方向上的子树深入下去（并不是两个方向上都需要深入，即剪枝）。
-
当\(k_j=1\)，就要求字典树中所表示串的第\(j\)位和\(S_{ij}\)异或的结果也是\(1\)，才有可能使得最终异或结果大于等于\(k\)，由于\(S_{ij}\oplus1\)与\(S_{ij}\)异或结果是\(1\)，故此时需要往\(S_{ij}\oplus1\)方向的那个子树上深入。
-
当\(k_j=0\)，说明字典树中所表示串的第\(j\)位和\(S_{ij}\)异或的结果可以是\(0\)，也可以是\(1\)
-
若字典树中所表示串的第\(j\)位和\(S_{ij}\)异或的结果是\(1\)，由于\(S_{ij}\oplus1\)与\(S_{ij}\)异或结果是\(1\)，即考虑往\(S_{ij}\oplus1\)方向，发现此时无需进行后续位的异或，也可知道最终异或结果大于\(k\)，故无需往\(S_{ij}\oplus1\)方向的子树下深入，直接利用往\(S_{ij}\oplus1\)方向的节点所附加的信息更新答案（别忘了，每个节点附加记录了这个节点所代表前缀最后一次在数列\(S_0,S_1,...,S_{i-1}\)中出现的位置，这是一种剪枝，也是优化的关键）。
-
若字典树中所表示串的第\(j\)位和\(S_{ij}\)异或的结果是\(0\)，由于\(S_{ij}\)与\(S_{ij}\)异或结果是\(0\)，即考虑往\(S_{ij}\)方向，此时还需要进行后续位的异或，故需要往\(S_{ij}\)方向的子树上深入。
-
假如逐位异或能够进行到最后一位，那说明异或到最后才比较出大于等于\(k\)，此时直接利用叶节点附加信息更新答案。
在\(S_i\)与字典树中的串进行带剪枝的逐位异或之后，就需要把\(S_i\)这个串插入到字典树中，注意插入过程需要更新节点的附加信息，以便后续计算。
时间复杂度分析：由于字典树只会往一个方向遍历，设整数序列最大的数为\(P\)，则树的最大深度是\(\log P\)，整数序列长度为\(n\)，故复杂度为\(O(n\log P)\)，本题中可以认为是\(O(30n)\)。
代码：
#include <algorithm>
#include <cassert>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 3e6 + 10;
int a[maxn];
int ch[maxm][2], val[maxm];
void solve() {
int n, k, tot = 1;
scanf("%d%d", &n, &k);
a[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
a[i] ^= a[i - 1];
}
ch[1][0] = ch[1][1] = 0;
val[1] = -1;
int ans_l = -1, ans_r = n + 1;
for (int i = 0; i <= n; i++) {
int now = 1, res = -1;
for (int j = 29; j >= 0; j--) {
int dig = (a[i] >> j) & 1;
if ((k >> j) & 1) { // k的当前位为1，只能和dig异或结果为1，才可能大于等于k
now = ch[now][dig ^ 1]; // 与dig异或结果为1的数是dig^1
} else { // k的当前位为0，和dig异或结果可以是1也可以是0
if (ch[now][dig ^ 1]) { // 和dig异或结果为1，后面的位都无须看，结果一定大于k
res = max(res, val[ch[now][dig ^ 1]]);
}
// 和dig异或结果是1的情况就无须遍历，只需要遍历和dig异或结果为0的情况
now = ch[now][dig];
}
if (now == 0) { // 节点没了
break;
}
}
if (now) res = max(res, val[now]);
if (res >= 0 && i - res < ans_r - ans_l) {
ans_l = res;
ans_r = i;
}
now = 1;
for (int j = 29; j >= 0; j--) {
int dig = (a[i] >> j) & 1;
if (!ch[now][dig]) {
ch[now][dig] = ++tot;
ch[tot][0] = ch[tot][1] = 0;
val[tot] = -1;
}
now = ch[now][dig];
val[now] = max(val[now], i);
}
}
if (ans_l == -1 && ans_r == n + 1) {
puts("-1");
} else {
printf("%d %d\n", ans_l + 1, ans_r);
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}