题目大意

给定整数序列 {an}\{a_n\}，寻找满足区间异或和大于等于 kk 的连续序列中最短的。

若有多个同样长度的答案，输出位置靠前的，若不存在输出 -1。

分析

看到异或最值就应该想到 01trie。做前缀异或和，这样我们的问题就变成找到最靠近的两个数，其异或大于等于 kk。

因为要求位置最靠前的，所以我选择倒着遍历。当遍历到第 ii 个数 aia_i 时，字典树已经维护好此位置之后的数据，即每个值出现最左边的位置。

const int maxn = 1e5 + 10, o = 30 - 1;

int trie[maxn * 30][2], val[maxn * 30], tot, n, k;

void insert(int ai, int i) {
	int p = 1;
	for (int j = o; j >= 0; j--) {
		int ch = (ai >> j) & 1;
		if (trie[p][ch] == 0)
			trie[p][ch] = ++tot;
		p = trie[p][ch];
		val[p] = i;
	}
}

我们只需从高位到低位遍历第 jj 位，分类讨论：

  • 若 k[j]=1k[j] = 1，则说明 ai[j]⊕au[j]a_i[j] \oplus a_u[j] 只能为 11，在字典树中选择 ai[j]⊕1a_i[j] \oplus 1 深入（什么都不做）。
  • 若 k[j]=0k[j] = 0，那么若 ai[j]⊕au[j]=1a_i[j] \oplus a_u[j] = 1 则一定大于 kk，记录字典树中 ai[j]⊕1a_i[j] \oplus 1 的值，然后在字典树中选择 ai[j]a_i[j] 深入。
int search(int ai, int i) {
	int p = 1, res = -1;
	for (int j = o; j >= 0; j--) {
		int x1 = (k >> j) & 1, x2 = (ai >> j) & 1;
		if (x1 == 0) {
			int tp = trie[p][x2 ^ 1];
			if (tp > 0)
				res = max(res, val[tp]);
		}
		p = trie[p][x1 ^ x2];
		if (p == 0)
			break;
	}
	if (p > 0)
		res = max(res, val[p]);
	return res;
}

因为我们是从前往后查的，因此同样长度中总是先查到考前的，汇总有

int main() {
	int ttt = rr();
	while (ttt--) {
		n = rr(), k = rr(), tot = 1;
		int anl = -1, anr = n + 1, pre_sum = 0;
		fill_n(trie[0], 2 * o * n, 0);

		for (int i = 1; i <= n; i++) {
			int ai = pre_sum ^ rr();
			int res = search(ai, i);
			if (res >= 0 && i - res < anr - anl)
				anl = res, anr = i;
			insert(ai, i);
			pre_sum = ai;
		}

		if (anl >= 0)
			printf("%d %d\n", anl + 1, anr);
		else
			printf("-1\n");
	}
	return 0;
}