CF617E XOR and Favorite Number（莫队算法）

题意

给你一个大小为n的序列，然后给你一个数字k，再给出m组询问，询问给出一个区间，问这个区间里面有多少个区间的异或结果为k。

分析

因为这题去学了莫队QAQ
首先记前缀异或和为 $s_i$si​，区间异或和为 $k$k的对数，等价于 $s_{r}xor{s}_{l-1}=k$sr​ xor sl−1​=k 的对数。如果 $r$r 确定了，那么 $s_{l-1}=s_{r}xork$sl−1​=sr​ xor k，相当于是在区间中，找某个数出现个数，这其实是莫队的模板题了。
将询问排序，左端点如果在同一块，就按右端点从小到大排序，否则按左端点所在的块排序。假设我们已经求出了 $[l,r]$[l,r] 这个区间，要转移到 $[l-1,r]$[l−1,r] 这个区间， $O\left(1\right)$O(1) 就可以转移。那么对于一个块，最多有 $\sqrt{n}$n ​ 个左端点，右端点最多遍布整个区间，也就是 $n$n，那么复杂度是 $O\left(n\sqrt{n}\right)$O(nn ​) 的。

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 2000005
using namespace std;
struct node{
	int l, r, i;
}q[N * 2];
LL z = 1, tot, ans[N];
int bl[N], s[N], k, cnt[N], blo;
int cmp(node x, node y){
	return bl[x.l] == bl[y.l]? (x.r < y.r): bl[x.l] < bl[y.l]; 
}
void add(int x){
	tot += cnt[s[x] ^ k];
	cnt[s[x]]++;
}
void del(int x){
	cnt[s[x]]--;
	tot -= cnt[s[x] ^ k];
}
int main(){
	int i, j, n, m, l, r;
	scanf("%d%d%d", &n, &m, &k);
	blo = n / sqrt(m * 2 / 3);
	if(!blo) blo = sqrt(n);
	for(i = 1; i <= n; i++){
		scanf("%d", &j);
		bl[i] = (i - 1) / blo + 1;
		s[i] = s[i - 1] ^ j;
	}
	for(i = 1; i <= m; i++){
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].i = i; q[i].l--; 
	}
	sort(q + 1, q + m + 1, cmp);
	l = 1, r = 0;
	for(i = 1; i <= m; i++){
		while(l < q[i].l) del(l), l++;
		while(l > q[i].l) l--, add(l);
		while(r < q[i].r) r++, add(r);
		while(r > q[i].r) del(r), r--;
		ans[q[i].i] = tot;
	}
	for(i = 1; i <= m; i++) printf("%lld\n", ans[i]);
	return 0;
}