codeforce617E-XOR and Favorite Number莫队+异或前缀和-白红宇

codeforce617E-XOR and Favorite Number莫队+异或前缀和

阅读量：4580 次

发布时间：2019-06-09

本文共 1478 字，大约阅读时间需要 4 分钟。

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

：https://blog.csdn.net/keyboarderqq/article/details/55807154

题意：

给出一系列数，对每个查询区间，计算有多少个子区间异或为k。

思路：

可以先预处理异或前缀，一个区间[L,R]的异或值=a[R]^a[L-1];

其中，a为异或前缀和数组；

如果当前区间是[A,B]，加一个右端点B+1，那么这个 B+1 的贡献就是[A,B]区间内有多少个a[x] = a[B+1]^k

那么我们可以每次记录cnt[a[x]]即cnt[a[B+1]^k]，并记录cnt[a[b+1]]++，同理左区间。

那么我们就可以使用莫队算法。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;typedef long long ll;const int maxn = 1<<20;ll a[maxn], flag[maxn];int pos[maxn];ll Ans = 0;ll res[maxn];int m,n,k;struct node { int l,r; int id;}Q[maxn];bool cmp(node a,node b){ if(pos[a.l]==pos[b.l]) return a.r < b.r; else return pos[a.l] < pos[b.l];}void add(int x){ Ans += flag[a[x]^k]; flag[a[x]]++;}void del(int x){ flag[a[x]]--; Ans -= flag[a[x]^k];}int main(){ scanf("%d%d%d", &n, &m, &k); int sz = sqrt(n); for(int i=1; i<=n; i++) { scanf("%I64d", &a[i]); a[i] = a[i-1] ^ a[i]; pos[i] = (i-1) / sz + 1; } flag[0] = 1; for(int i=1; i<=m; i++) { scanf("%d%d",&Q[i].l,&Q[i].r); Q[i].id = i; } sort(Q+1,Q+m+1,cmp); int l = 1,r = 0; for(int i=1; i<=m; i++) { while(l < Q[i].l){ del(l-1); l++; } while(l > Q[i].l){ l--; add(l-1); } while(r > Q[i].r){ del(r); r--; } while(r < Q[i].r){ r++; add(r); } res[Q[i].id] = Ans; } for(int i=1; i<=m; i++) { printf("%I64d\n",res[i]); } return 0;}

转载于:https://www.cnblogs.com/ckxkexing/p/8945473.html

你可能感兴趣的文章