[ codeforces ] Round #340 (Div. 2) E. XOR and Favorite Number

題目:
http://codeforces.com/contest/617/problem/E
給一個序列a1,a2,a3......an，再給一個k
接下來有m個詢問，給兩個數字l,r，問:
對於所有的i,j滿足l<=i<=j<=r，ai 到 aj所有數字的xor值=k的(i,j)有幾個

解法:
很直接就想到莫隊，關於該算法的實作就不多說了
先把序列做前綴xor再進行處理
注意計數用的陣列大小必須大於2^20 (1000000的二進位是11110100001001000000，但是兩個<1000000的數xor起來可以到11111111111111111111=(2^20)-1)
還有add,sub裡面操作的順序也要注意

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include<bits/stdc++.h> using namespace std; #define MAXN 100000 #define MAXQ 100000 struct Q{ int l,r,i,block; inline bool operator<(const Q &b)const{ return block==b.block?r<b.r:block<b.block; } }q[MAXQ+5]; int n,m,k; int s[MAXN+5]; long long ans[MAXQ+5]; int p[(1<<20)+1]; long long cur_ans; inline void add(int x){ cur_ans+=p[x^k]; ++p[x]; } inline void sub(int x){ --p[x]; cur_ans-=p[x^k]; } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;++i){ scanf("%d",&s[i]); s[i]^=s[i-1]; } int lim=1+(int)sqrt(n); for(int i=0;i<m;++i){ scanf("%d%d",&q[i].l,&q[i].r); --q[i].l; q[i].block=q[i].l/lim; q[i].i=i; } sort(q,q+m); for(int i=0,L=0,R=-1;i<m;++i){ while(R<q[i].r)add(s[++R]); while(L>q[i].l)add(s[--L]); while(R>q[i].r)sub(s[R--]); while(L<q[i].l)sub(s[L++]); ans[q[i].i]=cur_ans; } for(int i=0;i<m;++i)printf("%lld\n",ans[i]); return 0; }