请确保您接触过莫队再阅读此文：
对于所有询问，和普通莫队一样的分块然后排序。在这里只讨论 add 和 del 操作的具体实现。
题目中需要求一段区间的异或值，所以我们可以预处理序列 \(a\) 的“前缀异或值”pre_xor，题目中的 \(a_x \bigoplus a_{x+1} \bigoplus \dots \bigoplus a_y\) 可利用异或的性质转化为 pre_xor[y] ^ pre_xor[x - 1]。
这样，求区间 \([l,r]\) 中能够满足 \(a_x \bigoplus a_{x+1} \bigoplus \dots \bigoplus a_y = k\) 的 \(x,y\) 有多少组，就相当于求区间 \([l - 1,r]\) 中有多少组 pre_xor[y] ^ pre_xor[x - 1] == k。这就可以用莫队了。
显然，设 cnt[x] 代表数 \(x\) 的出现次数，则其可以与所有的 \(x \bigoplus k\) 配对即可。显然，在这里的 \(x\) 和 \(x \bigoplus k\) 一般是不用担心顺序的，总贡献为 cnt[x] * cnt[x ^ k]。
不过有一个特殊情况：当 \(k = 0\) 时，\(x = x \bigoplus k\)，这个时候就得特判贡献为 (cnt[x] * (cnt[x] - 1)) >> 1 了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,M = 1e5 + 9,SqrtN = 339,K = 1 << 20;
int n,m,k;
struct block{
int l,r;
} b[SqrtN];
int belong[N];
int block_len,block_cnt;
void build_block(){
block_len = block_cnt = (int)sqrt(n);
for(int i = 1;i <= block_cnt;i++){
b[i].l = b[i - 1].r + 1;
b[i].r = i * block_len;
}
b[block_cnt].r = n;
for(int i = 1;i <= block_cnt;i++)
for(int j = b[i].l;j <= b[i].r;j++)
belong[j] = i;
}
struct queries{
int l,r,id;
} q[M];
int a[N],pre_xor[N];
int cnt[K];
int ans[M],tmp;
int lres = 1,rres;
bool cmp(queries q1,queries q2){
return belong[q1.l] == belong[q2.l] ? belong[q1.r] < belong[q2.r] : belong[q1.l] < belong[q2.l];
}
void add(int x){
//tmp -= cnt[x] * (k ? cnt[x ^ k] : (cnt[x] - 1));
tmp -= k ? (cnt[x] * cnt[x ^ k]) : ((cnt[x] * (cnt[x] - 1)) >> 1);
cnt[x]++;
//tmp += cnt[x] * (k ? cnt[x ^ k] : (cnt[x] - 1));
tmp += k ? (cnt[x] * cnt[x ^ k]) : ((cnt[x] * (cnt[x] - 1)) >> 1);
}
void del(int x){
//tmp -= cnt[x] * (k ? cnt[x ^ k] : (cnt[x] - 1));
tmp -= k ? (cnt[x] * cnt[x ^ k]) : ((cnt[x] * (cnt[x] - 1)) >> 1);
cnt[x]--;
//tmp += cnt[x] * (k ? cnt[x ^ k] : (cnt[x] - 1));
tmp += k ? (cnt[x] * cnt[x ^ k]) : ((cnt[x] * (cnt[x] - 1)) >> 1);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
build_block();
for(int i = 1;i <= n;i++){
cin >> a[i];
pre_xor[i] = pre_xor[i - 1] ^ a[i];
}
for(int i = 1;i <= m;i++){
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1,q + m + 1,cmp);
for(int i = 1;i <= m;i++){
int L = q[i].l - 1,R = q[i].r;
while(lres > L)
add(pre_xor[--lres]);
while(rres < R)
add(pre_xor[++rres]);
while(lres < L)
del(pre_xor[lres++]);
while(rres > R)
del(pre_xor[rres--]);
ans[q[i].id] = tmp;
}
for(int i = 1;i <= m;i++)
cout << ans[i] << '\n';
return 0;
}