P4462 [CQOI2018] 异或序列
XichenOC
·
·
题解
P4462 [CQOI2018] 异或序列
题目翻译：
本题题意还算时比较简单明了的，我就不翻译了
思路：
$2.$ 根据上面性质可以发现最终要求的就是有多少 $r,l-1$ 可以使 $r \bigoplus l-1=k$ 又因为 $x \bigoplus y=k \rightarrow x \bigoplus k=y$ 因此可以用莫队来求解，答案增删的值就转换为当前增删点与 $k$ 异或的个数，用一个 $tot[i]$ 数组表示该前缀异或和数的个数，$sum[i]$ 表示前缀异或和。
```cpp
int cnt,tot[2*N],k;
void add(int x){
cnt+=tot[sum[x]^k];
tot[sum[x]]++;
}
void del(int x){
tot[sum[x]]--;
cnt-=tot[sum[x]^k];
}
```
$3.$ **注意**：由于是前缀异或和，所有的 $l$ 都要减一
# 完整代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N],sum[N],ans[N];
struct query{
int l,r,id;
}q[N];
int len;
bool cmp(query x,query y){
if(x.l/len!=y.l/len)return x.l<y.l;
else if((x.l/len)&1)return x.r<y.r;
else return x.r>y.r;
}
int cnt,tot[2*N],k;
void add(int x){
cnt+=tot[sum[x]^k];
tot[sum[x]]++;
}
void del(int x){
tot[sum[x]]--;
cnt-=tot[sum[x]^k];
}
signed main(){
int n,m;
scanf("%lld%lld%lld",&n,&m,&k);
len=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%lld",&sum[i]);
sum[i]^=sum[i-1];
}
for(int i=1;i<=m;i++){
int l,r;
scanf("%lld%lld",&l,&r);
q[i]={l,r,i};
}
sort(q+1,q+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
int ll=q[i].l-1;
int rr=q[i].r;
while(l<ll)del(l++);
while(l>ll)add(--l);
while(r<rr)add(++r);
while(r>rr)del(r--);
ans[q[i].id]=cnt;
}
for(int i=1;i<=m;i++){
printf("%lld\n",ans[i]);
}
}
```
## [莫队讲解](https://www.luogu.com.cn/article/bow29afg)