可持久化01字典树
作用：实现区间查询异或最大
时复：插入和查询都是O(logn)
算法流程
先开一个内存池，动态开点，每次插入一个数都建一个根节点，从根节点拉出一条链，链上的节点一边连向上一个版本的节点，一边连向新插入的点，再开一个num数组表示每一个节点经过了几次，查询时当高版本的num值大于低版本的num值时表示在这个区间内有对应的值，走到最后直接返回即可
题意
给定有初始值的n个数，m此操作，每次可以选择插入一个数或者查询一个区间内和给定的数异或最大是多少？
题解
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int MAXN=600000*40;
int ch[MAXN][2],rt[MAXN];
int val[MAXN],num[MAXN];
int tot,n,m,pre,tmp;
int insert(int last,int x){
int root=++tot,u=root;
for(int i=31;i>=0;i--){
int id=(x>>i)&1;
ch[u][id]=++tot;
ch[u][!id]=ch[last][!id];
num[ch[u][id]]=num[ch[last][id]]+1;
u=ch[u][id];
last=ch[last][id];
}
val[u]=x;
return root;
}
int query(int l,int r,int x){
if(l==r) return 0^x;
int ret=0;
for(int i=31;i>=0;i--){
int id=(x>>i)&1;
if(num[ch[r][!id]]>num[ch[l][!id]]){
if(!id==1) ret+=(1<<i);
l=ch[l][!id];
r=ch[r][!id];
}
else{
if(id==1) ret+=(1<<i);
l=ch[l][id];
r=ch[r][id];
}
}
return ret^x;
}
int main()
{
ios;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>tmp;
pre^=tmp;
rt[i]=insert(rt[i-1],pre);
}
while(m--){
char op;
cin>>op;
if(op=='A'){
cin>>tmp;
n++;
pre^=tmp;
rt[n]=insert(rt[n-1],pre);
}
else{
int l,r,x;
cin>>l>>r>>x;
if(l-1==0) cout<<query(0,rt[r-1],pre^x)<<'\n';
else cout<<query(rt[l-2],rt[r-1],pre^x)<<'\n';
}
}
return 0;
}
|
wechat
alipay