# 可持久化 01 字典树
作用：实现区间查询异或最大
时复：插入和查询都是 O (logn)
# 算法流程
先开一个内存池，动态开点，每次插入一个数都建一个根节点，从根节点拉出一条链，链上的节点一边连向上一个版本的节点，一边连向新插入的点，再开一个 num 数组表示每一个节点经过了几次，查询时当高版本的 num 值大于低版本的 num 值时表示在这个区间内有对应的值，走到最后直接返回即可
# P4735 最大异或和
# 题意
给定有初始值的 n 个数，m 此操作，每次可以选择插入一个数或者查询一个区间内和给定的数异或最大是多少？
# 题解
# 代码
#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'; // 注意这里如果 l-1 已经等于 0 了，则直接查询 0 到 r-1 范围即可 | |
else cout<<query(rt[l-2],rt[r-1],pre^x)<<'\n'; | |
} | |
} | |
return 0; | |
} | |
/* | |
5 1 | |
2 6 4 3 6 | |
Q 3 5 4 | |
*/ |
