codeforces 617 E

题目链接：https://codeforces.com/contest/617/problem/E

莫队模板题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2000010;

int t, len, n, m, k, tot; ll ans = 0;;
int a[maxn], b[maxn], c[maxn], sum[maxn];
int L[maxn], R[maxn], pos[maxn];

struct Query{
	int l, r, id;
	ll ans; 
}q[maxn];

bool cmp_L(Query a, Query b){
	if(a.l == b.l) return a.r < b.r;
	return a.l < b.l;
}

bool cmp_R(Query a, Query b){
	if(a.r == b.r) return a.l < b.l;
	return a.r < b.r;
}

bool cmp_id(Query a, Query b){
	return a.id < b.id;
}

void add(int x, int v){
	if(v > 0) {
		ans += c[sum[x - 1] ^ k];
		++c[sum[x - 1]];
	}
	else {
		ans += c[sum[x] ^ k];
		++c[sum[x]];
	}
}

void del(int x){
	--c[sum[x - 1]];
	ans -= c[sum[x - 1] ^ k];
}

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
		n = read(), m = read(), k = read();
		int mx = 0;
		for(int i = 1 ; i <= n ; ++i) a[i] = read(), b[i] = a[i], sum[i] = sum[i - 1] ^ a[i], mx = max(mx, sum[i]);

		t = sqrt(n), len = m / t;
		for(int i = 1 ; i <= t ; ++i){
			L[i] = (i - 1) * len + 1;
			R[i] = i * len;
		}
		if(R[t] < m) {
			L[++t] = R[t - 1] + 1;
			R[t] = m;
		}
		
		for(int i = 1 ; i <= t ; ++i){
			for(int j = L[i] ; j <= R[i] ; ++j){
				pos[j] = i;
			}
		}
		
		int l, r;
		for(int i = 1 ; i <= m ; ++i){
			q[i].l = read(), q[i].r = read();
			q[i].id = i;
		} 
		
		sort(q + 1, q + 1 + m, cmp_L);
		
		for(int i = 1 ; i <= t ; ++i){
			for(int j = 0 ; j <= mx ; ++j) c[j] = 0;
			
			sort(q + L[i], q + 1 + R[i], cmp_R);

			ans = 0;
			int ql = q[L[i]].l, qr = q[L[i]].r, cl = ql, cr = qr;
			
			++c[sum[ql - 1]];
			for(int j = ql ; j <= qr ; ++j){
				ans += c[sum[j] ^ k];
				++c[sum[j]]; 
			}
			
			q[L[i]].ans = ans;
			
			for(int j = L[i] + 1 ; j <= R[i] ; ++j){
				while(cl < q[j].l) del(cl++);
				while(cl > q[j].l) add(--cl, 1);
				while(cr < q[j].r) add(++cr, -1);
				q[j].ans = ans;
			}
		}
		
		sort(q + 1, q + 1 + m, cmp_id);
		for(int i = 1 ; i <= m ; ++i){
			printf("%lld
", q[i].ans);
		}
	return 0;
}