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

· · 题解

打广告->这里

我蠢了……

如果a_{l} xor ...a_{r}=k，那么只要记一下异或前缀和sum，然后看是否sum_r\ xor\ sum_{l-1}=k就好了……

然后考虑一下每次转移，因为范围很小，只要记录一下区间内每个数出现的次数，然后答案加上cnt[sum_{now}\ xor\ k]就好了……O(1)转移，莫队能过

然后因为sum_r\ xor\ sum_{l-1}是区间[l,r]的答案，所以每一次只要删到l-1就行了，这个可以在读入的时候就预处理掉，就是把每一个区间的l减一

我就是因为上面这一点死活调不对

然后顺便记得一开始l要设为0

注意插入的时候先处理答案后插入点，删除的时候先删除点后处理答案

否则的话试一下下面这组数据

4 5 0

1 1 1 1

1 4

1 3

2 3

2 4

4 4

答案应该是

4

2

1

2

0

upd(2019.1.15)：数据太水莫队的时候顺序乱来都能过，于是我test完之后好像贴了个错的代码上来……感谢@NaCly_Fish指出我的错误……顺便提醒我要开long long

// luogu-judger-enable-o2
//minamoto
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=100005;
int a[N],cnt[N],n,m,k,l,r,ans[N],rt[N],ansn,s;
struct node{
    int l,r,id;
    inline bool operator <(const node b)const
    {
        if(rt[l]!=rt[b.l]) return l<b.l;
        return rt[l]&1?r<b.r:r>b.r;
    }
}q[N];
inline void add(int x){
    ++cnt[x],ansn+=cnt[x^k];
}
inline void del(int x){
    ansn-=cnt[x^k],--cnt[x];
}
int main(){
    n=read(),m=read(),k=read(),s=sqrt(n);
    for(int i=1;i<=n;++i) a[i]=read()^a[i-1],rt[i]=i/s;
    for(int i=1;i<=m;++i)
    q[i].l=read()-1,q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m);
    l=0,r=0,cnt[0]=1;
    for(int i=1;i<=m;++i){
        while(l>q[i].l) add(a[--l]);
        while(r<q[i].r) add(a[++r]);
        while(l<q[i].l) del(a[l++]);
        while(r>q[i].r) del(a[r--]);
        ans[q[i].id]=ansn;
    }
    for(int i=1;i<=m;++i) print(ans[i]);
    Ot();
    return 0; 
}