莫队算法模板

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int N = 1<<20;
 5 struct node
 6 {
 7     int l,r,id;
 8 }Q[N];
 9 
10 int ans[N];
11 long long answer[N];
12 long long flag[N];
13 int a[N];
14 bool cmp(node x,node y)
15 {
16     if(ans[x.l]==ans[y.l])
17         return x.r<y.r;
18     return ans[x.l]<ans[y.l];
19 }
20 int n,m,k;
21 int L = 1,R = 0;
22 long long Ans= 0;
23 void add(int x)
24 {
25     Ans+=flag[a[x]^k];
26     flag[a[x]]++;
27 }
28 void del(int x)
29 {
30     flag[a[x]]--;
31     Ans-=flag[a[x]^k];
32 }
33 int main()
34 {
35 
36     scanf("%d%d%d",&n,&m,&k);
37     int sz = sqrt(n);
38     for(int i = 1; i <= n; i++){
39         scanf("%d",&a[i]);
40         a[i] = a[i-1]^a[i];
41         ans[i] = i/sz;
42     }
43     flag[0] = 1;
44     for(int i = 1; i <= m; i++)
45     {
46         scanf("%d%d",&Q[i].l,&Q[i].r);
47         Q[i].id = i;
48     }
49     sort(Q+1,Q+m+1,cmp);
50     for(int i = 1; i <= m; i++)
51     {
52         while(L<Q[i].l)
53         {
54             del(L-1);
55             L++;
56         }
57         while(L>Q[i].l)
58         {
59             L--;
60             add(L-1);
61         }
62         while(R<Q[i].r)
63         {
64             R++;
65             add(R);
66         }
67         while(R>Q[i].r)
68         {
69             del(R);
70             R--;
71         }
72         answer[Q[i].id] = Ans;
73     }
74     for(int i = 1; i <= m; i++)
75     {
76         printf("%lld
",answer[i]);
77     }
78     return 0;
79 }