luoguP4462 [CQOI2018]异或序列

Isonan · 2018-09-23 19:49:58 · 题解

原题传送门>Here<

异或有一个很重要的性质：它的逆运算就是自身。

维护该数列的前缀异或和XOR[i]，然后一边莫队一边维护count[j]表示XOR[i]=j的个数

每次加入一个点i时，ans+=count[XOR[i]^k]。

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
#define nowl num[i-1].l
#define nowr num[i-1].r

int n,m,k,XOR[100001],at[400001],nowans,pos[100001],ans[100001],block;
void del(int x){nowans-=at[k^XOR[x]];at[XOR[x]]--;}
void add(int x){nowans+=at[k^XOR[x]];at[XOR[x]]++;}
struct point{int l,r,orig;}num[100001];
bool cmp(point a,point b){return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l;}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    block=(int)sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",XOR+i),XOR[i]^=XOR[i-1],pos[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++)scanf("%d%d",&num[i].l,&num[i].r),num[i].orig=i,num[i].l--;
    std::sort(num+1,num+m+1,cmp);
    for(int i=num[1].l;i<=num[1].r;i++)add(i);
    ans[num[1].orig]=nowans;
    for(int i=2;i<=m;i++){
        if(num[i].l<nowl)for(int j=num[i].l;j<nowl;j++)add(j);
        else for(int j=nowl;j<num[i].l;j++)del(j);
        if(num[i].r<nowr)for(int j=nowr;j>num[i].r;j--)del(j);
        else for(int j=nowr+1;j<=num[i].r;j++)add(j);
        ans[num[i].orig]=nowans;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}