CODEFORCES 340 XOR and Favorite Number 莫队模板题

原来我直接学的是假的莫队

原题：

Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k.

1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000, 0 ≤ ai ≤ 1 000 000

题意：

给定一个数列a[i]，你可以通过异或前缀和求出s[i]，每次求出[l-1,r]内s[i] xor s[j]=k的(i,j)的对数

模板题，先分块，左端点所在块为第一关键字，右端点为第二关键字排序

然后记录一个l和r，每次直接暴力让l和r走到查询的两端点即可

我之前一直以为块间跳转是当两端点中间有一个或多个块的时候加上中间的块的值

经过jjh和sqy大神的指点才知道原来分块就是指排序的时候分块，处理的时候暴力走就可以了

我学了假的分块

有一些细节需要注意，首先所有的操作都是建立在异或前缀和上的所以输入的时候要搞前缀和，而且算答案的时候l要-1

一般n<1e5求数对的个数一般会爆int，要注意longlong

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<vector>

 using namespace std;

 #define ll long long

 int rd(){int z=,mk=;  char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')mk=-;  ch=getchar();}

     while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-'';  ch=getchar();}

     return z*mk;

 }

 struct dcd{int x,y,id;}b[];

 int n,m,k,a[];

 int blck;

 ll cnt[],ans[];

 ll bwl=;

 inline void ist(int x){  bwl+=cnt[a[x]^k],++cnt[a[x]];}

 inline void dlt(int x){  --cnt[a[x]],bwl-=cnt[a[x]^k];}

 bool cmp(dcd x,dcd y){  return(x.x/blck==y.x/blck)?(x.y<y.y):(x.x/blck<y.x/blck);}

 int main(){//freopen("ddd.in","r",stdin);

     cin>>n>>m>>k;  blck=(int)sqrt(n*1.0);

     for(int i=;i<=n;++i)  a[i]=rd(),a[i]^=a[i-];

     for(int i=;i<=m;++i)  b[i].x=rd(),b[i].y=rd(),b[i].id=i;

     sort(b+,b+m+,cmp);

     int l=,r=;  cnt[]=;

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

         while(l<b[i].x)  dlt(l-),++l;

         while(l>b[i].x)  l--,ist(l-);

         while(r<b[i].y)  ist(++r);

         while(r>b[i].y)  dlt(r--);

         ans[b[i].id]=bwl;

     }

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

     return ;

 }

巴特西

CODEFORCES 340 XOR and Favorite Number 莫队模板题

最新文章

热门文章