[CQOI2018]异或序列

传送门

题意：

已知一个长度为n的整数数列$a_1,a_2,…,a_n$,给定查询参数l、r,问在$a_l,a_{l+1},…,a_r$区间内，有多少子序列满足异或和等于k。也就是说，对于所有的$x,y (I ≤ x ≤ y ≤ r)$,能够满足$a_x \bigoplus a_{x+1} \bigoplus … \bigoplus a_y = k$的$x,y$有多少组。

数据范围：$1≤n,m≤10^5,0≤k,a_i≤10^5,1≤l_j≤r_j≤n$

解法：

​ 维护一个异或前缀和序列，表示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]];}

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