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

· · 题解

莫队

异或，真是个神东西!!!

首先异或和满足前缀，也就是说设sum[i]为a[1]^a[2]^...^a[i]，那么a[i]^a[i+1]^...^a[j]=sum[j]^sum[i-1]

而且异或不仅满足交换律，而且对于a^b=c时，a^c=b，b^c=a这两个式子同样成立

那么就好做了，假设当前i到j这个子串的异或和为k，就说明sum[j]^sum[i-1]=k，也就是sum[i-1]^k=sum[j]，sum[j]^k=sum[i-1]

然后在区间转移的时候，设cnt[i]为当前区间值为i的前缀有多少个，然后对于增加序列长度的操作，假设新加的位置为r+1，我们先将cnt[sum[r+1]]++，然后求出ans+=cnt[sum[r+1]^k]，左边扩展也是如此，不过注意，向左扩展时，对ans的更新是用sum[l-1]的，因为是sum[j]与sum[i-1]可以满足前缀

而且向右扩展的时候，如果sum[r+1]^k=sum[l-1]的话，ans++，因为我们更新的时候没有计算[l...r+1]区间的影响，所以要维护一下

而对于区间缩小的情况，就ans先减，再更新cnt，因为要先消除贡献再减cnt，其它步骤类似就好了

最后黏上代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MA 100005
using namespace std;
int n,m,k,pos[MA];
int c[MA],sum[MA],cnt[MA<<1];
struct data{
    int l,r,num;
    int res;
}a[MA];
inline bool cmp(const data &x,const data &y){
    if(pos[x.l]==pos[y.l]) return x.r<y.r;
    return x.l<y.l;
}
inline bool cmp2(const data &x,const data &y){
    return x.num<y.num;
}
inline void motm(){
    int i,j;
    int l=1,r=0,ans=0;
    for(i=1;i<=m;i++){
        for(;r<a[i].r;){
            r++;
            cnt[sum[r]]++;
            ans+=cnt[sum[r]^k];
            if((sum[r]^k)==sum[l-1]) ans++;
        }
        for(;r>a[i].r;){
            ans-=cnt[sum[r]^k];
            cnt[sum[r]]--;
            if((sum[r]^k)==sum[l-1]) ans--;
            r--;
        }
        for(;l<a[i].l;){
            ans-=cnt[sum[l-1]^k];
            cnt[sum[l]]--;
            l++;
        }
        for(;l>a[i].l;){
            l--;
            cnt[sum[l]]++;
            ans+=cnt[sum[l-1]^k];
        }
        a[i].res=ans;
    }
    return ;
}
int main(){
    int i;
    scanf("%d %d %d",&n,&m,&k);
    int blk=(int)(sqrt(n));
    for(i=1;i<=n;i++){
        scanf("%d",&c[i]);
        sum[i]=sum[i-1]^c[i];
        pos[i]=(i-1)/blk+1;
    }
    for(i=1;i<=m;i++){
        scanf("%d %d",&a[i].l,&a[i].r);
        a[i].num=i;
    }
    sort(a+1,a+m+1,cmp);
    motm();
    sort(a+1,a+n+1,cmp2);
    for(i=1;i<=m;i++){
        printf("%d\n",a[i].res);
    }
    return 0;
}

本人蒟蒻，不喜勿喷