思路:
经典莫队,维护每个元素的前缀异或,在每次左端点移动的时候统计s[l-1]^k出现的次数,右端点移动的时候统计s[r]^k出现的次数,就可以得到答案了
注意int会爆。
1 #include<cstdio> 2 #include<cctype> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 inline int getint() { 7 char ch; 8 while(!isdigit(ch=getchar())); 9 int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return x; 12 } 13 int base; 14 struct Que { 15 int l,r,id; 16 bool operator < (const Que &x) const { 17 return (r/base<x.r/base)?true:((r/base==x.r/base)?(l<x.l):false); 18 } 19 }; 20 const int N=1<<20; 21 long long cnt[N]={1},Ans=0; 22 int k; 23 inline void inc(const int s) { 24 Ans+=cnt[s^k]; 25 cnt[s]++; 26 } 27 inline void dec(const int s) { 28 cnt[s]--; 29 Ans-=cnt[s^k]; 30 } 31 int main() { 32 int n=getint(),m=getint(); 33 k=getint(); 34 base=(int)sqrt(n); 35 int s[n+1]; 36 s[0]=0; 37 for(int i=1;i<=n;i++) s[i]=s[i-1]^getint(); 38 Que q[m]; 39 for(int i=0;i<m;i++) { 40 q[i].l=getint()-1; 41 q[i].r=getint(); 42 q[i].id=i; 43 } 44 std::sort(&q[0],&q[m]); 45 long long ans[m]; 46 for(int i=0,l=0,r=0;i<m;i++) { 47 while(r<q[i].r) inc(s[++r]); 48 while(r>q[i].r) dec(s[r--]); 49 while(l<q[i].l) dec(s[l++]); 50 while(l>q[i].l) inc(s[--l]); 51 ans[q[i].id]=Ans; 52 } 53 for(int i=0;i<m;i++) printf("%I64d ",ans[i]); 54 return 0; 55 }