思路：
莫队的思路还是比较好想的，对给出的序列求前缀和之后，如果a i ⊕ a i + 1 ⊕ a i + 2 … … ⊕ a j = k，则s u m i − 1 ⊕ s u m j = k.
考虑离线计算，由于x ⊕ y = z等价于x ⊕ z = y，所以在增加一个数x的时候，跟x异或起来为k的数都有贡献，用c n t [ i ]表示i出现的次数，维护一下就好了。
还有一种用树状数组+扫描线的写法，但是全01序列就会被卡成O ( n 2 ),了解思想就好了吧。
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; typedef long long ll; ll n,m,k,a[maxn],ans[maxn],res,cnt[maxn*2],sum[maxn],len; struct node{ ll l,r,id; }q[maxn]; bool cmp(node a,node b){ if(a.l/len==b.l/len) return a.r<b.r; return a.l/len<b.l/len; } void add(int x){ res+=cnt[a[x]^k]; cnt[a[x]]++; } void del(int x){ cnt[a[x]]--; res-=cnt[a[x]^k]; } int main(){ cin>>n>>m>>k; len=sqrt(n); for(int i=1;i<=n;i++) cin>>a[i],a[i]^=a[i-1]; for(int i=1;i<=m;i++){ cin>>q[i].l>>q[i].r;q[i].id=i; q[i].l--; } sort(q+1,q+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++){ int ql=q[i].l,qr=q[i].r; while(l<ql){ del(l);l++; } while(l>ql){ l--;add(l); } while(r>qr){ del(r);r--; } while(r<qr){ r++;add(r); } ans[q[i].id]=res; } for(int i=1;i<=m;i++) cout<<ans[i]<<endl; return 0; }
