CodeForces 617 E. XOR and Favorite Number

题目链接：

题目描述：

　　给出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 <math.h>
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <iostream>
 9 #include <algorithm>
10 using namespace std;
11 
12 typedef __int64 LL;
13 const int maxn = 100010;
14 struct node
15 {
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<m; i++)
36     {
37         while (r < q[i].r)
38         {
39             r ++;
40             tmp += num[b[r]^k];
41             num[b[r]] ++;
42         }
43 
44         while (r > 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<m; i++)
83         {
84             scanf ("%d %d", &q[i].l, &q[i].r);
85             q[i].id = i;
86         }
87 
88         sort (q, q+m, cmp);
89 
90         solve();
91 
92         for (int i=0; i<m; i++)
93             printf ("%I64d
", ans[i]);
94     }
95     return 0;
96 }