洛谷 4735 可持久化字典树

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxx = 6e5+10;
 4 int trie[32*maxx][2],val[32*maxx],sum[32*maxx];
 5 int rt[maxx],s[maxx],tot;
 6 void update(int u,int x)
 7 {
 8     rt[u]=++tot;
 9     int now=rt[u],pre=rt[u-1];
10     for(int i=31;i>=0;i--){
11         int id=(x>>i)&1;
12         trie[now][id]=++tot;
13         trie[now][id^1]=trie[pre][id^1];
14         now=trie[now][id];
15         pre=trie[pre][id];
16         sum[now]=sum[pre]+1;
17     }
18     val[now]=x;
19 }
20 int query(int l,int r,int x)
21 {
22     for(int i=31;i>=0;i--){
23         int id=(x>>i)&1;
24         if(sum[trie[r][id^1]]>sum[trie[l][id^1]])
25             r=trie[r][id^1],l=trie[l][id^1];
26         else r=trie[r][id],l=trie[l][id];
27     }
28     return val[r]^x;
29 }
30 int main(){
31     int n,m,x;
32     scanf("%d%d",&n,&m);
33     rt[0]=++tot;
34     for(int i=1;i<=n;i++){
35         scanf("%d",&x);
36         s[i]=s[i-1]^x;
37         update(i,s[i]);
38     }
39     char op[2];
40     int l,r;
41     while(m--){
42         scanf("%s",op);
43         if(op[0]==‘A‘){
44             n++;
45             scanf("%d",&x);
46             s[n]=s[n-1]^x;
47             update(n,s[n]);
48         }
49         else{
50             scanf("%d%d%d",&l,&r,&x);
51             l--,r--;
52             if(l==0&&r==0)printf(“%d\n”,s[n]^x);    //防止造成一段空区间
53             else printf("%d\n",query(rt[max(l-1,0)],rt[r],s[n]^x)); 
54         }
55     }
56 }