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

zhangyuxing · 2019-12-14 09:08:14 · 题解

首先考虑

区间异或，考虑前缀异或和。

用 pre_i 表示 a_1⨁a_2⨁...⨁a_i

可以把条件两边异或一个 pre_{x-1} 变换为：

这个东西显然也可写作

于是询问 (x,y) 就变成了求 pre_{x-1},pre_x,...,pre_y 当中有多少对数 (p,q) 满足 p⨁k=q

区间相关，可离线，于是考虑莫队。

考虑加减元素咋搞。

我们发现变动一个x的时候，受影响的是 x⨁k ，因此\Delta{ans}=cnt_{x⨁k}。

代码就容易写出，注意每次减节点的时候操作的是 l-1

code in c++

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,k,block,res,pre[100005],ans[100005],cnt[100005];
struct query{
    int l,r,num;
} q[maxn];
bool cmp(query a,query b){return (a.l/block)^(b.l/block)?a.l<b.l:a.r<b.r;}
void add(int x){res+=cnt[pre[x]^k];++cnt[pre[x]];}
void del(int x){--cnt[pre[x]];res-=cnt[pre[x]^k];}
int main()
{
    int l=1,r=0,ql,qr,i;
    scanf("%d%d%d",&n,&m,&k);block=sqrt(n);
    for(i=1;i<=n;++i)scanf("%d",&pre[i]),pre[i]^=pre[i-1];
    for(i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i;
    sort(q+1,q+1+m,cmp);
    cnt[0]=1;
    for(i=1;i<=m;++i)
    {
        ql=q[i].l;qr=q[i].r;
        while(r<qr)add(++r);
        while(r>qr)del(r--);
        while(l<ql)del(l-1),++l;
        while(l>ql)--l,add(l-1);
        ans[q[i].num]=res;
    }
    for(i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}