BZOJ 3261: 最大异或和 可持久化trie

模板题，刷点数据结构 ~ 

code: 

#include <bits/stdc++.h> 
#define N 600009   
#define setIO(s) freopen(s".in","r",stdin)    
using namespace std;    
int rt[N],sum[N],tot;   
struct node 
{ 
    int ch[2],cnt;   
}t[N*28];     
void insert(int a,int b,int len,int num) 
{ 
    if(len<0)  return; 
    int o=(num>>len)&1;        
    t[b].ch[o^1]=t[a].ch[o^1];         
    t[b].ch[o]=++tot;   
    t[t[b].ch[o]].cnt=t[t[a].ch[o]].cnt+1;             
    insert(t[a].ch[o],t[b].ch[o],len-1,num);                          
}
int query(int l,int r,int len,int x) 
{
    if(len<0) return 0;               
    int o=(x>>len)&1;               
    if(t[t[r].ch[o^1]].cnt>t[t[l].ch[o^1]].cnt) 
    {          
        return (1<<len)+query(t[l].ch[o^1],t[r].ch[o^1],len-1,x);      
    }
    else 
    {
        return query(t[l].ch[o],t[r].ch[o],len-1,x);       
    }      
}
int main() 
{
    // setIO("input");    
    int i,j,n,m;   
    scanf("%d%d",&n,&m); 
    rt[0]=++tot;        
    insert(0,rt[0],25,0);                                       
    for(i=1;i<=n;++i) 
    {   
        int x;       
        scanf("%d",&x);     
        sum[i]=sum[i-1]^x;  
        rt[i]=++tot;                   
        insert(rt[i-1],rt[i],25,sum[i]);          
    }
    for(i=1;i<=m;++i) 
    {             
        char str[10]; 
        scanf("%s",str);   
        if(str[0]=='A') 
        {   
            int b; 
            scanf("%d",&b); 
            ++n; 
            sum[n]=sum[n-1]^b;      
            rt[n]=++tot; 
            insert(rt[n-1],rt[n],25,sum[n]);             
        } 
        else 
        { 
            int x,y,z; 
            scanf("%d%d%d",&x,&y,&z);     
            --x,--y;                                
            if(x==0)    printf("%d
",query(0,rt[y],25,z^sum[n]));   
            else printf("%d
",query(rt[x-1],rt[y],25,z^sum[n]));   
        }
    }
    return 0; 
}