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

· · 题解

解法：

​ 维护一个异或前缀和序列，表示1到i的异或和，之后问题就变成了：区间[l-1,r]中，有多少对数异或为k，开个桶记录异或值，直接莫队即可。

代码：

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int l,h,r;
}q[100001];
int o[200001],bl[100001],n,m,ans,r; //o[i]表示当前区间有多少个数异或和为i
int a[100001],num[100001],k,blo,l;
inline bool cmp(node c,node d){
    if (bl[c.l]!=bl[d.l]) return c.l<d.l;
    if (bl[c.l]&1) return c.r<d.r; return c.r>d.r;
}
inline void add(int x){ans+=o[a[x]^k]; o[a[x]]++;}
inline void del(int x){o[a[x]]--; ans-=o[k^a[x]];}
int main(){
    scanf("%d%d%d",&n,&m,&k); blo=sqrt(n);
    for (int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        bl[i]=(i-1)/blo+1;
        a[i]=a[i-1]^a[i];
    }
    for (int i=1; i<=m; i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].h=i; q[i].l--;
    }
    sort(q+1,q+m+1,cmp); l=1;
    for (int i=1; i<=m; i++){
        while (l>q[i].l) l--,add(l);
        while (l<q[i].l) del(l),l++;
        while (r<q[i].r) r++,add(r);
        while (r>q[i].r) del(r),r--;
        num[q[i].h]=ans;
    }
    for (int i=1; i<=m; i++) printf("%d\n",num[i]);
    return 0;
}

2019/1/15 update:

被 @NaCly_Fish 神仙hack掉了，原先的题解中del函数有问题，应改成这样：

inline void del(int x){o[a[x]]--; ans-=o[k^a[x]];}

写的时候为了好看没过脑子就写上了