Description

已知一个长度为 n 的整数数列 a[1],a[2],…,a[n] ，给定查询参数 l、r ，问在 [l,r] 区间内，有多少连续子

序列满足异或和等于 k 。

也就是说，对于所有的 x，y (l≤x≤y≤r)，能够满足a[x]^a[x+1]^…^a[y]=k的x，y有多少组。

Input

输入文件第一行，为3个整数n，m，k。

第二行为空格分开的n个整数，即ai，a2,…．an。

接下来m行，每行两个整数lj，rj，表示一次查询。

1≤n，m≤105，O≤k，ai≤105，1≤lj≤rj≤n

Output

输出文件共m行，对应每个查询的计算结果。

Sample Input

4 5 1

1 2 3 1

1 4

1 3

2 3

2 4

4 4

Sample Output

4

2

1

2

1

Solution

不能再这么颓下去了

昨天打了一天板子感觉现在脑子锈了QAQ……

题意杀了好久……明明子序列应该是不连续的

一看题目这个形式基本莫队没跑了，

然而如果两端加入/减掉一个数，这个数对于区间的影响是靠近它的连续一段

这显然是没法维护的。所以可以维护一个异或前缀和sum

因为a[x] xor a[x+1]……xor a[y-1] xor a[y] 等价于 sum[y] xor sum[x-1]

那么我们就可以用莫队来维护前缀和了。

每次往莫队里加入/删除前缀和的时候只需要考虑有多少个数与当前数异或等于k，开个桶即可。

因为查询区间[x,y]的时候我们需要sum[x-1]~sum[y]，所以读入的时候左端点要减一。

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define N (500000+100) 7 using namespace std; 8  9 struct node{
    int x,y,num,id,ans;}ask[N];10 int Keg[N],sum[N],n,m,k,x,now;11 12 bool cmp1(node a,node b){
    return a.id==b.id?a.y
           
            
             ask[i].x) Ins(--l);37 while (r
             
              ask[i].y) Del(r--);39 ask[i].ans=now;40 }41 42 sort(ask+1,ask+m+1,cmp2);43 for (int i=1; i<=m; ++i)44 printf("%d\n",ask[i].ans);45 }