区间莫队+异或前缀和
假设p[i]表示a[1]^a[2]....a[i]
那么
a[i]^a[i+1]....^a[j]=p[j]^p[i-1]
对于每一个新增的询问a[x],增加的个数为a[x]^k出现的数目
代码:
#include<iostream> #include<algorithm> #include<cmath> #define ll long long using namespace std; const int maxn=1<<20; ll flag[maxn];//存每一个前缀抑或出现次数 int a[maxn];//存放异或前缀和 ll ans[maxn];//存放答案 int pos[maxn];//存放区间 struct node { int l,r,id; }Q[maxn]; bool cmp(node a,node b)//查询区间排序 { if(pos[a.l]==pos[b.l]) return a.r<b.r; return pos[a.l]<pos[b.l]; } int L=1,R=0; ll Ans=0; int n,m,k; void add(int x) { Ans+=flag[a[x]^k]; flag[a[x]]++; } void del(int x) { flag[a[x]]--; Ans-=flag[a[x]^k]; } int main() { scanf("%d%d%d",&n,&m,&k); int block=sqrt(n); for(int i=1;i<=n;i++) { //scanf("%d",&a[i]); cin>>a[i]; a[i]=a[i]^a[i-1]; pos[i]=i/block; } for(int i=1;i<=m;i++) { //scanf("%d%d",&Q[i].l,&Q[i].r); cin>>Q[i].l>>Q[i].r; Q[i].id=i; } sort(Q+1,Q+1+m,cmp); flag[0]=1; for(int i=1;i<=m;i++) { while(L<Q[i].l) { del(L-1); L++; } while(L>Q[i].l) { L--; add(L-1); } while(R<Q[i].r) { R++; add(R); } while(R>Q[i].r) { del(R); R--; } ans[Q[i].id]=Ans; } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }