题目链接：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<iostream> #include<cstdio> using 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(k<0){ 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(k<0)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<=n;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<=m;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 ",query(root[r-1],s[n]^x,23,l-1)); } } }