题解 P4462 【[CQOI2018]异或序列】

数据结构学傻了导致看到这道题只想着线段树…… 其实是莫队的，$O(N\sqrt{N})$的复杂度可以毫不费力的通过$O(10^5)$的数据范围 不会莫队的话请出门左转小Z的袜子……包教包会 然后这里介绍一个比较好写的莫队写法，我们单独考虑挪动左端点和右端点的情况 ，这样的话就不需要讨论两个区间的重叠情况了，然后插入的时候是前++，--，删除的时候是后++，--，因为我们必须保证当前的左端点，右端点是已经存在的点而不是别的东西…… 但是我们会发现这样的话会在两个区间完全没有交点的时候多删除一些点或者多插入一些点，而这在某些题里面是不允许的(尽管这道题里面正的点和负的点会消掉但是有些题不允许)所以我们直接特判下两个区间不重叠的情况然后重构整个区间就可以了 对于莫队的具体做法就是先预处理出来异或前缀和，方便求区间异或值 然后我们维护一个当前区间里每个值有多少个数，然后插入的时候求一下这个区间里有多少个值为k^a\[r]的数就可以了，注意插入的时候先处理答案后插入点，删除的时候先删除点后处理答案即可。 然后代码会非常的好写~ ```C #include<cstdio> #include<algorithm> #include<cmath> using namespace std;const int N=1e5+10;typedef long long ll; int bs;int n;int m;int k;int val[N];ll nowans;int nl;int nr=-1; struct query{int p;int l;int r;ll ans;}q[N];int a[N]; inline bool cmp1(const query& a,const query& b){return a.l>b.l;} inline bool cmp2(const query& a,const query& b){return a.r<b.r;} inline bool cmp3(const query& a,const query& b){return a.p<b.p;} int main() { scanf("%d%d%d",&n,&m,&k);bs=sqrt(m); for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]^=a[i-1];}//离线 for(int i=1,l,r;i<=m;i++){scanf("%d%d",&l,&r);q[i]=(query){i,l-1,r,0};}//对询问分块 sort(q+1,q+m+1,cmp1);for(int i=1;i<=m;i+=bs){sort(q+i,q+min(i+bs,m+1),cmp2);} for(int i=1;i<=m;i++) { if(nr<q[i].l)//判一下区间重叠 { for(int p=nl;p<=nr;p++){val[a[p]]--;}nowans=0;nl=q[i].l;nr=q[i].r; for(int p=nl;p<=nr;p++){nowans+=val[k^a[p]];val[a[p]]++;} } else //单独考虑左端点和右端点就好了~ { for(;nl<q[i].l;){val[a[nl]]--;nowans-=val[k^a[nl++]];} for(;nl>q[i].l;){nowans+=val[k^a[--nl]];val[a[nl]]++;} for(;nr>q[i].r;){val[a[nr]]--;nowans-=val[k^a[nr--]];} for(;nr<q[i].r;){nowans+=val[k^a[++nr]];val[a[nr]]++;} }q[i].ans=nowans; }sort(q+1,q+m+1,cmp3); for(int i=1;i<=m;i++){printf("%lld\n",q[i].ans);}return 0;//拜拜程序~ } ```