如果我们对给定的序列求出异或意义下的前缀和，哪么题意变为求满足 \(sum_{i-1} \operatorname{xor} sum_j=k\) 的 \((i,j)\) 数量。
由于 \(x \operatorname{xor} y=z\) 等价于 \(x \operatorname{xor} z=y\)，所以在加上数 \(x\) 的时候，\(\forall a \operatorname{xor} x=k\) 的 \(a\) 都有贡献。于是我们用 \(cnt_i\) 表示 \(i\) 的出现次数，离线莫队维护即可。
//617E. XOR and Favorite Number
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
struct Query
{
ll l,r,id;
}q[MAXN];
ll n,m,k,a[MAXN],ans[MAXN],t,num,belong[MAXN],cnt[MAXN<<1],now;
bool cmp(Query a,Query b)
{
return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
void add(int x)
{
now+=cnt[x^k];
cnt[x]++;
return;
}
void del(int x)
{
cnt[x]--;
now-=cnt[x^k];
return;
}
int main()
{
ll l,r,ql,qr;
scanf("%lld%lld%lld",&n,&m,&k);
t=sqrt(n);
num=ceil(n*1.0/t);
for(int i=1;i<=num;i++)
{
for(int j=(i-1)*t+1;j<=i*t;j++)
{
belong[j]=i;
}
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i]^=a[i-1];//用 a[i] 存异或意义下的前缀和
}
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(&q[1],&q[m+1],cmp);
l=1;
r=0;
for(int i=1;i<=m;i++)
{
ql=q[i].l-1;
qr=q[i].r;
while(l<ql)
{
del(a[l++]);
}
while(l>ql)
{
add(a[--l]);
}
while(r<qr)
{
add(a[++r]);
}
while(r>qr)
{
del(a[r--]);
}
ans[q[i].id]=now;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i]);
}
return 0;
}
/*
* CF
* https://codeforces.com/problemset/problem/617/E
* C++20 -O0
* 2022.10.2
*/