CQOI2018异或序列 [莫队]

莫队板子 用于复习

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define Sqr(x) ((x)*(x))
using namespace std;
const int N = 1e5 + 5;
struct Q{
	int x, y, id;
}q[N];
int n, m, k, res;
int cnt[N << 1], sum[N], a[N], ans[N];
int bl[N], blsize;

bool rule(Q x, Q y){return bl[x.x] == bl[y.x] ? x.y < y.y : x.x < y.x;}

inline void ins(int x){
    res += cnt[k ^ sum[x]];
    ++cnt[sum[x]];	
}
inline void del(int x){
	--cnt[sum[x]];
    res -= cnt[k ^ sum[x]];	
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	blsize = sqrt(n);
	bl[0] = 1;
	for(int i = 1; i <= n; ++i){
		scanf("%d", &a[i]);
		sum[i] = sum[i - 1] ^ a[i];
	    bl[i] = i / blsize + 1;
	}
	for(int i = 1; i <= m; ++i)
	    scanf("%d%d", &q[i].x, &q[i].y), --q[i].x, q[i].id = i;
	sort(q + 1, q + m + 1, rule);
	int l = 1, r = 0;
	for(int i = 1; i <= m; ++i){
		while(l > q[i].x) ins(--l);
	    while(l < q[i].x) del(l++);
		while(r > q[i].y) del(r--);
		while(r < q[i].y) ins(++r);
		ans[q[i].id] = res;
	}
	for(int i = 1; i <= m; ++i)
		printf("%d
", ans[i]);
    return 0;
}