E. XOR and Favorite Number
                                       617E
                            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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#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);
}