CodeForces - 617E
给n个数， m个询问， 每次询问问你[l, r]区间内有多少对(i, j), 使得a[i]^a[i+1]^......^a[j]结果为k。（注意 i ！ = j）
维护一个前缀异或值就可以了。要注意的是 区间[l, r]， 我们需要将pre[l-1]......pre[r]都加进去， pre[l-1]不能少。
#include<bits/stdc++.h>
using namespace std;
#define maxn 1234567
#define ll long long
ll s[1<<22],n,m,k,col[maxn],B,sum,ans[maxn],pre[maxn],l,r;
struct node
{
int l,r,id;
bool operator<(const node &b)const
{
return l/B==b.l/B?r<b.r:l<b.l;
}
} a[maxn];
void del(int x)
{
s[pre[x]]--;
sum-=s[k^pre[x]];
}
void add(int x)
{
sum+=s[k^pre[x]];
s[pre[x]]++;
}
int main()
{
r=-1;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1; i<=n; i++)
{
scanf("%lld",&col[i]);
pre[i]=pre[i-1]^col[i];
}
B=sqrt(n);
for(int i=0; i<m; i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i;
a[i].l--;
}
sort(a,a+m);
for(int i=0; i<m; i++)
{
while(l<a[i].l)
del(l++);
while(r>a[i].r)
del(r--);
while(l>a[i].l)
add(--l);
while(r<a[i].r)
add(++r);
ans[a[i].id]=sum;
}
for(int i=0; i<m; i++)printf("%lld\n",ans[i]);
return 0;
}