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\n", ans[i]);

    return 0;

}
秒客网

CQOI2018异或序列 [莫队]

相关文章
