[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 I: qwb VS 去污棒 [可持久化01字典树]【数据结构】

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
 
# define abs(x) (((x)>0)?(x):-(x))
 
const int N = 400000+10;
const int MOD  = 1e8;
 
int read(){
    int x=0;char ch = getchar();
    while('0'>ch||ch>'9')ch=getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x;
}
 
/**********************************/

int trie[N*40][2],sz[N*40],rt[N];
int n,m,cnt,sum;
char s[10];
 
int update(int pre,int i,int x){
    int now=++cnt;
    if(0==i){
        trie[now][0]=trie[now][1]=0;
        sz[now]=sz[pre]+1;
        return now;
    }
    int bt=((x>>(i-1))&1);
    trie[now][1-bt]=trie[pre][1-bt];
    trie[now][bt]=update(trie[pre][bt],i-1,x);
    sz[now]=sz[trie[now][0]]+sz[trie[now][1]];
    return now;
}
 
int query(int rt1,int rt2,int i,int x){
    if (i==0) return 0;
    int bt=((x>>(i-1))&1);
    if (sz[trie[rt2][1-bt]]-sz[trie[rt1][1-bt]])
        return (1<<(i-1))+query(trie[rt1][1-bt],trie[rt2][1-bt],i-1,x);
    else
        return query(trie[rt1][bt],trie[rt2][bt],i-1,x);
}
 
int main(){
    int _=read(),kcase=0;
    while(_--){
        n=read(),m=read();
        rt[0]=trie[0][0]=trie[0][1]=sz[0]=sum=0;
        rt[0]=update(rt[0],25,0);
        for (int i=1;i<=n;i++){
            sum^=read();
            rt[i]=update(rt[i-1],25,sum);
        }
 
        printf("Case %d:\n",++kcase);
        while (m--){
            int l,r;
            scanf("%s",s+1);
            if (s[1]=='1'){
                sum^=read();
                n++;rt[n]=update(rt[n-1],25,sum);
            }
            else{
                l=read()-1,r=read()-1;
                printf("%d\n",query(rt[l-1],rt[r],25,sum^read()));
            }
        }
    }
    return 0;
}