bzoj3261: 最大异或和

bzoj3261: 最大异或和

---

就是个裸的可持久化Trie = = 而且这东西就和可持久化线段树一毛一样，甚至不用上网搜板子就能自己打出来= =

用可持久化Trie记录后缀异或和，打一个全局标记p，表示Trie上的所有数都要异或p。插入数x的时候先插入p再把p异或上x

询问就变成了(Max_{l<=p<=r}S_p ext{ xor }x ext{ xor }p)

询问还是那样询问，只不过把x异或一个p就行了

#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,p;
int rt[600001],ch[20000000][2],tot[20000000],cnt,id;
il vd cp(int a,int b){ch[b][0]=ch[a][0],ch[b][1]=ch[a][1],tot[b]=tot[a];}
il vd ins(int x){
    rt[++cnt]=++id;
    cp(rt[cnt-1],rt[cnt]);
    int y=rt[cnt];
    for(int i=23;~i;--i){
        ++tot[y];
        int t=(p>>i)&1;
        cp(ch[y][t],++id);
        ch[y][t]=id;
        y=ch[y][t];
    }
    ++tot[y];
    p^=x;
}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<=n;++i)ins(gi());
    char opt[2];
    while(m--){
        scanf("%s",opt);
        if(opt[0]=='A')ins(gi());
        else{
            int l=gi()-1,r=gi(),k=gi()^p;
            int x=rt[l],y=rt[r],ans=0;
            for(int i=23;~i;--i){
                int t=(k>>i)&1;
                if(tot[ch[y][!t]]!=tot[ch[x][!t]])ans+=1<<i,x=ch[x][!t],y=ch[y][!t];
                else x=ch[x][t],y=ch[y][t];
            }
            printf("%d
",ans);
        }
    }
    return 0;
}