标签：题目 mit 第一个 get 除了 分支 root test har
题目链接：https://www.acwing.com/problem/content/258/
题目给出长度为n的序列，操作有两种，求[p,n]段的异或和再与x的异或，或者增加一个数x，使用可持久化Trie和异或前缀和可以解决，但是需要在[l-1,r-1]区间内，右区间自然满足，左区间的话需要加上latest标记，使得当前访问结点的版本是属于l-1或者之后的。时间复杂度为O((n+m)*32)。
代码：
#include
#includeusing namespace std;
const int maxn = 600010;
int s[maxn],root[maxn],n,m,tot;
int trie[maxn*24][2],latest[maxn*24];
void insert(int i,int k,int p,int q){
if(k0){
latest[q]=i;
return;
}
int c=(s[i]>>k)&1;
//除了当前的c分支外所有的分支都指向p的分支
if(p)trie[q][c^1] =trie[p][c^1];
trie[q][c]=++tot;//当前开一条新的链
insert(i,k-1,trie[p][c],trie[q][c]);
latest[q]=max(latest[trie[q][0]],latest[trie[q][1]]);
}
int query(int now,int val,int k,int limit){
if(k0)return s[latest[now]]^val;
int c=(val>>k) &1;
if(latest[trie[now][c^1]]>=limit)
//一定有一个子节点是满足的 ，否则不可能进入now结点
return query(trie[now][c^1],val,k-1,limit);
else return query(trie[now][c],val,k-1,limit);
}
int main(){
cin>>n>>m;
latest[0]=-1;
root[0]=++tot;//插入n+1个数，第一个是0
insert(0,23,0,root[0]);
for(int i=1;i){
int x;
scanf("%d",&x);
s[i]=s[i-1]^x;
root[i]=++tot;
insert(i,23,root[i-1],root[i]);
}
for(int i=1;i){
char op[2];
scanf("%s",op);
if(op[0]==‘A‘){
int x;
scanf("%d",&x);
++n;
s[n]=s[n-1]^x;
root[n]=++tot;
insert(n,23,root[n-1],root[n]);
}else{
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",query(root[r-1],s[n]^x,23,l-1));
}
}
}
《算法竞赛进阶指南》0x48可持久化数据结构 可持久化Trie
标签：题目 mit 第一个 get 除了 分支 root test har
原文地址：https://www.cnblogs.com/randy-lo/p/13375613.html