Codeforces 617E：XOR and Favorite Number（莫队算法）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://codeforces.com/problemset/problem/617/E

题意：给出n个数，q个询问区间，问这个区间里面有多少个区间[i,j]可以使得ai^ai+1^...^aj = k。

思路：根据xor的性质，可以处理出前缀异或和sum[]，那么要使结果等于k，就是sum[i-1]^sum[j] == k，即sum[j]^k == sum[i-1]，那么用一个数组cnt[]存储对于每一个sum[]的数量。然后用莫队算法做。莫队算法是一种离线处理区间问题的算法，在我看来是将询问通过分块排序成一个可以暴力处理的序列，让暴力的复杂度尽量的低。只有O（n*sqrt（n））的复杂度。

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 #include <algorithm>

 #include <string>

 #include <iostream>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 typedef long long LL;

 #define N 100010

 #define INF 0x3f3f3f3f

 struct node {

     int l, r, id;

     LL ans;

 } q[N*];

 int sum[N], kuai, k;

 LL cnt[N*];

 bool cmp1(const node &a, const node &b) {

     if(a.l / kuai != b.l / kuai) return a.l / kuai < b.l / kuai; // 根据块的编号排序

     return a.r < b.r; // 块内按照r值排序

 }

 bool cmp2(const node &a, const node &b) {

     return a.id < b.id;

 }

 int main()

 {

     int n, m, num, L, R;

     LL s = ;

     scanf("%d%d%d", &n, &m, &k);

     for(int i = ; i <= n; i++) {

         scanf("%d", &num); sum[i] = sum[i-] ^ num;

     }

     for(int i = ; i <= m; i++) {

         scanf("%d%d", &q[i].l, &q[i].r);

         q[i].id = i; q[i].l--;

     }

     kuai = sqrt(n);

     sort(q + , q +  + m, cmp1);

     L = ; R = ;

     for(int i = ; i <= m; i++) {

         int l = q[i].l, r = q[i].r;

         while(L < l) {

             cnt[sum[L]]--;

             s -= cnt[sum[L]^k];

             L++;

         }

         while(L > l) {

             L--;

             s += cnt[sum[L]^k];

             cnt[sum[L]]++;

         }

         while(R < r) {

             R++;

             s += cnt[sum[R]^k];

             cnt[sum[R]]++;

         }

         while(R > r) {

             cnt[sum[R]]--;

             s -= cnt[sum[R]^k];

             R--;

         }

         q[i].ans = s;

     }

     sort(q + , q +  + m, cmp2);

     for(int i = ; i <= m; i++) printf("%lld\n", q[i].ans);

     return ;

 }