XOR and Favorite Number题解
XOR and Favorite Number题解
思路引导
这一道题主要是为了说明莫队算法和分块之间的联系。
先主要讲讲莫队的用处吧。
它是个离线算法，维护两个指针l,r。
移动l和r的时候顺便进行更改，维护好l-r区间内的某个值。
对于询问区间的排序，遵循l所在的分块相同，其次是r的先后顺序。
现在来说说本题：
关键在于莫队维护什么
我加入一个数p时，我就知道了他的亦或前缀和。
那现在我想要在这个区间内找到有多少个抑或前缀和与之抑或后为k。
这个区间指的是l到p这个区间。
显然k已知，那么这个抑或前缀和也已知，只需要知道这个东西出现的次数就好啦。
稍微注意一下l的-1问题即可。
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
关键在于莫队维护什么
我加入一个数p时，我就知道了他的亦或前缀和。
那现在我想要在这个区间内找到有多少个抑或前缀和与之抑或后为k。
这个区间指的是p+1到r这个区间。
显然k已知，那么这个抑或前缀和也已知，只需要知道这个东西出现的次数就好啦。
*/
#define ingrp(x) ceil(1.0*x/sq)
int sq,n,m,k;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
inline void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
int num[100005];
int pre[100005];
struct nod{
int le;
int ri;
int id;
}line[100005];
int ans[100005];
int cnt[2000006];
int sum,l,r;
void add(int x){
sum+=cnt[pre[x]^k];
cnt[pre[x]]++;
}
void del(int x){
cnt[pre[x]]--;
sum-=cnt[pre[x]^k];
}
bool cmp(nod x,nod y){
int x1=ingrp(x.le);
int x2=ingrp(y.le);
if(x1!=x2){
return x1<x2;
}
else return x.ri<y.ri;
}
void mvftL(int goal){
while(l-1>=goal){
add(l-1);
l--;
}
}
void mvbkL(int goal){
while(l+1<=goal){
del(l);
l++;
}
}
void mvftR(int goal){
while(r-1>=goal){
del(r);
r--;
}
}
void mvbkR(int goal){
while(r+1<=goal){
add(r+1);
r++;
}
}
signed main(){
n=read();
sq=floor(1.0*sqrt(n));
m=read();
k=read();
for(int i=1;i<=n;i++){
num[i]=read();
pre[i]=pre[i-1]^num[i];
}
for(int i=1;i<=m;i++){
line[i].le=read();
line[i].le--;
line[i].ri=read();
line[i].id=i;
}
sort(line+1,line+1+m,cmp);
add(line[1].le);
l=line[1].le;
r=line[1].le;
for(int i=1;i<=m;i++){
int ll=line[i].le;
int rr=line[i].ri;
int id=line[i].id;
mvftL(ll);
mvbkL(ll);
mvftR(rr);
mvbkR(rr);
ans[id]=sum;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
}