区间异或

题意

给出\(n\)个数，求出有多少个区间\([l,r]\)满足这个区间的异或和\(\geq k\)。
\(n\leq 10^6\)，数字，\(k\leq 10^9。\)

思路

设\(s_i\)为前缀区间异或和，根据异或的运算规律，可得\([l,r]\)异或和即为\(s_r\ xor\ s_{l-1}\)。
所以题目所求即为对于一个\(r\)，有多少个\(l\)满足\(s_r\ xor\ s_{l-1}\geq k\)。

如果所求为\(s_r\ xor\ s_{l-1}= k\)，可用\(trie\)解决，即根据\(s_r\)和\(k\)上的每一位在\(trie\)上遍历出\(s_{l-1}\)。
对于\(>k\)的部分，在\(trie\)上遍历\(s_r\ xor\ s_{l-1}= k\)时，我们求得的\(s_{l-1}\)是\(k\)的前缀（因还没遍历完后面的位置），如果发现\(k\)的这一位为\(0\)时，让求得的数这一位为\(1\)，后面的位数不用考虑，就满足了\(>k\)。
举个例子，比如\(k\)是\(010110\)，那么求\(s_r\ xor\ s_{l-1}\)是\(1*****\),\(011***\),\(010111\)的方案数即可

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int t, n, k, s, tot;
long long ans;
int trie[30000001][2], cnt[30000001];

void insert(int x) {
	int p = 1;
	cnt[p]++;
	for (int i = 30; i >= 0; i--)
		if (1 << i & x) {
			if (!trie[p][1]) trie[p][1] = ++tot;
			p = trie[p][1];
			cnt[p]++;
		} else {
			if (!trie[p][0]) trie[p][0] = ++tot;
			p = trie[p][0];
			cnt[p]++;
		}
}

int query(int x) {
	int p = 1, res = 0;
	for (int i = 30; i >= 0; i--) {
		if (!p) break;
		if (1 << i & x) {
			if (1 << i & k) p = trie[p][0];//让x_l-1顺着x^x_l-1=k的方向走
			else res += cnt[trie[p][0]], p = trie[p][1];//如果k这一位为0，那么我们的答案可以加上这一位x^x_l-1为1的方案
		} else {
			if (1 << i & k) p = trie[p][1];//同上理
			else res += cnt[trie[p][1]], p = trie[p][0];
		}
	}
	return res + cnt[p];//最后的是x^x_l-1=k的方案
}

signed main() {
	scanf("%d %d", &n, &k);
	memset(cnt, 0, sizeof(cnt));
	memset(trie, 0, sizeof(trie));
	s = ans = 0, tot = 1;
	insert(0);
	for (int i = 1, a; i <= n; i++) {
		scanf("%d", &a);
		s ^= a;
		ans += query(s);
		insert(s);
	}
	printf("%lld\n", ans);
}

区间异或

原文：https://www.cnblogs.com/HSZGB/p/14042835.html