E. XOR and Favorite Number
                            time limit per test4 seconds
                        memory limit per test256 megabytes
                                inputstandard input
                                outputstandard output

Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k.

Input The first line of the input contains integers n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000) — the length of the array, the number of queries and Bob's favorite number respectively.

The second line contains n integers ai (0 ≤ ai ≤ 1 000 000) — Bob's array.

Then m lines follow. The i-th line contains integers li and ri (1 ≤ li ≤ ri ≤ n) — the parameters of the i-th query.

Output Print m lines, answer the queries in the order they appear in the input.

Sample test(s) input 6 2 3 1 2 1 1 0 3 1 6 3 5 output 7 0 input 5 3 1 1 1 1 1 1 1 5 2 4 1 3 output 9 4 4

。。好题，我一开始觉得一定是按分块分的可持久化字典树，具体做法呢就是先利用莫队算法，然后将区间内的所有a[i]都加入字典树，然后对于每个节点我们都有对应能异或得k的所有对应节点，然后我们边修改l和r边修改ans。 然后因为位数在20左右，所以非常完美，不会爆炸。

以上都是yy，其实这题只要用一个sum【i】数组存一个前缀异或和，sum[r]^sum[l-1]就是a[l]到a[r]的异或和了，这样我们每加入一个sum[i]都有对应的op[sum[i]]，这样我们再记录一个cnt[i]代表目前a[j]值为i的j的个数 这样ans就能+=cnt[i]*cnt[op[i]]，此外，如果k=0，那么便有l=r的情况出现，然而k=0我们只需要特殊处理即可，此题还需要注意longlong，反正我把全部int改成long long了。 代码：

include

include

include

include

include

include

define ll long long

struct wow{ ll id,ans,l,r; }ans[1000005]; ll l,r,mx,a[1000005],block,n,m,k,now,cnt[2000005],sum[1000005],op[2000005],pos[1000005]; bool cmp1(wow q,wow w){ if (pos[q.l]==pos[w.l]) return q.r<w.r; return pos[q.l]<pos[w.l]; } bool cmp2(wow q,wow w){ return q.id<w.id; } void updata(ll x,ll v){ if (k!=0) now-=cnt[sum[x]]*cnt[op[sum[x]]]; else now-=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2; cnt[sum[x]]+=v; if (k!=0) now+=cnt[sum[x]]*cnt[op[sum[x]]]; else now+=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2; } int main(){ //freopen("tx.in","r",stdin); scanf("%I64d%I64d%I64d",&n,&m,&k); block=sqrt(n); for (int i=1;i<=n;i++) pos[i]=i/block; for (int i=1;i<=n;i++) scanf("%I64d",&a[i]); for (int i=1;i<=n;i++) sum[i]=sum[i-1]^a[i],mx=std::max(mx,sum[i]); for (int i=0;i<=mx;i++) op[i]=i^k; for (int i=1;i<=m;i++){ scanf("%I64d%I64d",&ans[i].l,&ans[i].r); ans[i].l--; ans[i].id=i; ans[i].ans=0; }
std::sort(ans+1,ans+1+m,cmp1); l=ans[1].l;r=ans[1].l;cnt[sum[l]]++;now=0; for (int i=1;i<=m;i++){ if (l<ans[i].l){ for (int j=l;j<ans[i].l;j++) updata(j,-1); } else if (l>ans[i].l){ for (int j=l-1;j>=ans[i].l;j--) updata(j,1); } l=ans[i].l; if (r<ans[i].r){ for (int j=r+1;j<=ans[i].r;j++) updata(j,1); } else if (r>ans[i].r){ for (int j=r;j>ans[i].r;j--) updata(j,-1); } r=ans[i].r; ans[i].ans=now;
} std::sort(ans+1,ans+1+m,cmp2); for (int i=1;i<=m;i++) printf("%I64d\n",ans[i].ans); }