题目链接：

　　

题目描述：

　　给出n个数，m次查询，每次查询在区间[l, r]里面有多少对(i, j)，满足a_i ^ a_i+1 ^ a_i+2 ^ ...... ^ a_j-1 ^ a_j == k

解题思路：

　　莫队算法，在线性复杂度内进行转移，问题关键在与如何进行状态转移，我们设定 sum[i] 为[1, i]区间内的异或和，对于区间[a, b]的异或和为sum[b] ^ sum[a-1]。如果区间 [a, b] 的异或和为k，则有sum[b] ^ sum[a-1] == k，由于异或的性质可以推论出：sum[b] ^ k == sum[a-1]，sum[a-1] ^ k == sum[b]。

1 /** 2     ans要用LL， 3     num[]要在k的范围内扩大两倍 4 */ 5 #include 
     
       6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 using namespace std;11 12 typedef __int64 LL;13 const int maxn = 100010;14 struct node15 {16     int l, r, id;17 } q[maxn];18 LL ans[maxn];19 int b[maxn], num[maxn*20];20 int n, m, k, lb;21 22 bool cmp (node x, node y)23 {24     if (x.l / lb == y.l / lb)25         return x.r < y.r;26     return x.l < y.l;27 }28 void solve ()29 {30     int l, r;31     LL tmp;32     l = r = tmp = 0;33     num[0] = 1;34 35     for (int i=0; i
          
            q[i].r)45 {46 num[b[r]] --;47 tmp -= num[b[r]^k];48 r --;49 }50 51 while (l < q[i].l - 1)52 {53 num[b[l]] --;54 tmp -= num[b[l] ^ k];55 l ++;56 }57 58 while (l > q[i].l - 1)59 {60 l --;61 tmp += num[b[l] ^ k];62 num[b[l]] ++;63 }64 65 ans[q[i].id] = tmp;66 }67 }68 69 int main ()70 {71 while(scanf ("%d %d %d", &n, &m, &k) != EOF)72 {73 b[0] = 0;74 lb = (int) sqrt (n);75 76 for (int i=1; i<=n; i++)77 {78 scanf ("%d", &b[i]);79 b[i] ^= b[i-1];80 }81 82 for (int i=0; i