【模板】可持久化trie（luoguP4735）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 6e5+9;
 4 struct Trie{
 5     int cnt;
 6     int tr[N*30][2],sum[N*30];
 7     int insert(int las,int val){
 8         int tem , now;
 9         tem = now = ++cnt;
10         for(int i = 23;i>=0;--i){
11             tr[now][0] = tr[las][0];
12             tr[now][1] = tr[las][1];
13             sum[now] = sum[las] + 1;
14             bool t = (1<<i) & val;
15             las = tr[las][t];
16             tr[now][t] = ++cnt;
17             now = tr[now][t];
18         }
19         sum[now] = sum[las] + 1;
20         return tem;
21     }
22     int query(int l,int r,int val){
23         int tem = 0;
24         for(int i = 23;i>=0;--i){
25             bool t = (1<<i) & val;
26             if( sum[ tr[r][t^1] ] - sum[ tr[l][t^1] ] ){
27                 tem |= (1<<i);
28                 r = tr[r][t^1];
29                 l = tr[l][t^1];
30             }
31             else r = tr[r][t] , l = tr[l][t];
32         }
33         return tem;
34     }
35 }trie;
36 int a[N],b[N],root[N];
37 char s[10];
38 int main(){
39     int n,m; scanf("%d %d",&n,&m);
40     ++n;
41     for(int i = 2;i<=n;++i) scanf("%d",a+i);
42     for(int i = 1;i<=n;++i) b[i] = b[i-1] ^ a[i];
43     for(int i = 1;i<=n;++i) root[i] = trie.insert(root[i-1],b[i]);
44     for(int i = 1;i<=m;++i){
45         scanf("%s",s);
46         if( s[0] == ‘A‘){
47             ++n;
48             scanf("%d",a+n);
49             b[n] = b[n-1] ^ a[n];
50             root[n] = trie.insert(root[n-1],b[n]);
51         }
52         else{
53             int l,r,x; scanf("%d %d %d",&l,&r,&x);
54             printf("%d\n",trie.query(root[l-1],root[r],b[n]^x));
55         }
56     }
57     return 0;
58 }