洛谷P4462 [CQOI2018]异或序列（莫队）

打广告->[这里](https://www.cnblogs.com/bztMinamoto/p/9538115.html)

我蠢了……

如果$a_{l} xor ...a_{r}=k$，那么只要记一下异或前缀和$sum$，然后看是否$sum_r\ xor\ sum_{l-1}=k$就好了……

然后考虑一下每次转移，因为范围很小，只要记录一下区间内每个数出现的次数，然后答案加上$cnt[sum_{now}\ xor\ k]$就好了……$O(1)$转移，莫队能过

然后因为$sum_r\ xor\ sum_{l-1}$是区间$[l,r]$的答案，所以每一次只要删到$l-1$就行了，这个可以在读入的时候就预处理掉，就是把每一个区间的$l$减一

我就是因为上面这一点死活调不对

然后顺便记得一开始$l$要设为0

注意插入的时候先处理答案后插入点，删除的时候先删除点后处理答案

否则的话试一下下面这组数据

4 5 0

1 1 1 1

1 4

1 3

2 3

2 4

4 4

答案应该是

upd(2019.1.15)：数据太水莫队的时候顺序乱来都能过，于是我test完之后好像贴了个错的代码上来……感谢@NaCly_Fish指出我的错误……顺便提醒我要开long long
```
// luogu-judger-enable-o2
//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
inline int read(){
#define num ch-'0'
char ch;bool flag=0;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*10+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x){
if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=100005;
int a[N],cnt[N],n,m,k,l,r,ans[N],rt[N],ansn,s;
struct node{
int l,r,id;
inline bool operator <(const node b)const
{
if(rt[l]!=rt[b.l]) return l<b.l;
return rt[l]&1?r<b.r:r>b.r;
}
}q[N];
inline void add(int x){
++cnt[x],ansn+=cnt[x^k];
}
inline void del(int x){
ansn-=cnt[x^k],--cnt[x];
}
int main(){
n=read(),m=read(),k=read(),s=sqrt(n);
for(int i=1;i<=n;++i) a[i]=read()^a[i-1],rt[i]=i/s;
for(int i=1;i<=m;++i)
q[i].l=read()-1,q[i].r=read(),q[i].id=i;
sort(q+1,q+1+m);
l=0,r=0,cnt[0]=1;
for(int i=1;i<=m;++i){
while(l>q[i].l) add(a[--l]);
while(r<q[i].r) add(a[++r]);
while(l<q[i].l) del(a[l++]);
while(r>q[i].r) del(a[r--]);
ans[q[i].id]=ansn;
}
for(int i=1;i<=m;++i) print(ans[i]);
Ot();
return 0;
}
```

巴特西

洛谷P4462 [CQOI2018]异或序列（莫队）

最新文章

热门文章