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

· · 题解

cf原题？

为了方便，我们维护一下异或前缀和。

显然是一个莫队板子..

这道题需要在意一下左端点

如果原数组是a[l]，前缀和数组是val[l]的话。 a[l]=val[l]^val[l-1] 所以我们删除l的时候，实际上需要删除的是l-1

代码：

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,k,blo,val[maxn],d[maxn],ans,flag[maxn];
struct cqoi{
    int x,y,ans,id;
} orz[maxn];
bool cmp(cqoi s1,cqoi s2){
    if(d[s1.x]==d[s2.x]) return s1.y<s2.y;
    return s1.x<s2.x;
}
bool cmp2(cqoi s1,cqoi s2){
    return s1.id<s2.id;
}
void update(int u,int opt)
{
    if(!opt){
        flag[val[u]]--;
        ans-=flag[val[u]^k];
    } else{
        ans+=flag[val[u]^k];
        flag[val[u]]++;
    }
}

void sc()
{
    scanf("%d%d%d",&n,&m,&k);blo=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]),d[i]=(i-1)/blo,val[i]^=val[i-1];
    for(int i=1;i<=m;i++) scanf("%d%d",&orz[i].x,&orz[i].y),orz[i].id=i;
    sort(orz+1,orz+1+m,cmp);
}

int main()
{
    sc();
    int l=1,r=0;
    flag[0]=1;
    for(int i=1;i<=m;i++)
    {
        while(r<orz[i].y) update(++r,1);
        while(r>orz[i].y) update(r--,0);
        while(l<orz[i].x) update(l-1,0),l++;
        while(l>orz[i].x) l--,update(l-1,1);
        orz[i].ans=ans;
    }
    sort(orz+1,orz+1+m,cmp2);
    for(int i=1;i<=m;i++) printf("%d\n",orz[i].ans);
    return 0;
}
/*
4 1 1
1 2 3 1
2 3
*/