可持久化01trie类似主席树思想 但是不支持版本差（也可以加一个siz 做差） 只能再维护一个左端点的最大值即可
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int t[N<<5][2],Lmax[N<<5],ncnt,n,m,x,y,z,T[N],s[N]; char ss[2]; void upnode(int k,int i,int pre,int pos) { if(k<0){Lmax[pos]=i;return ;} bool c=(s[i]>>k)&1; if(pre)t[pos][c^1]=t[pre][c^1]; t[pos][c]=++ncnt; upnode(k-1,i,t[pre][c],t[pos][c]); Lmax[pos]=max(Lmax[t[pos][0]],Lmax[t[pos][1]]); } int qmax(int k,int val,int l,int pos) { if(k<0)return val^s[Lmax[pos]]; bool c=(val>>k)&1; if(Lmax[t[pos][c^1]]>=l)return qmax(k-1,val,l,t[pos][c^1]); else return qmax(k-1,val,l,t[pos][c]); } int main() { scanf("%d%d",&n,&m);Lmax[0]=-1; T[0]=++ncnt;upnode(23,0,0,T[0]); rep(i,1,n) { int x;scanf("%d",&x); s[i]=s[i-1]^x; T[i]=++ncnt; upnode(23,i,T[i-1],T[i]); }int l,r; while(m--) { scanf("%s",ss); if(ss[0]=='A') { int x;scanf("%d",&x);n++;s[n]=s[n-1]^x; T[n]=++ncnt;upnode(23,n,T[n-1],T[n]); } else { scanf("%d%d%d",&l,&r,&x); int val=x^s[n]; printf("%d ",qmax(23,val,l-1,T[r-1])); } } return 0; }
正常主席树写法
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int t[N<<5][2],ncnt,n,m,x,y,z,T[N],s[N],siz[N<<5]; char ss[2]; void upnode(int k,int val,int pre,int &pos) { pos=++ncnt; t[pos][0]=t[pre][0];t[pos][1]=t[pre][1];siz[pos]=siz[pre]+1; if(k<0)return ; int c=(val>>k)&1; upnode(k-1,val,t[pre][c],t[pos][c]); } int qmax(int k,int val,int pre,int pos) { if(k<0)return 0; int c=(val>>k)&1; int si=siz[t[pos][c^1]]-siz[t[pre][c^1]]; if(si)return (1<<k)+qmax(k-1,val,t[pre][c^1],t[pos][c^1]); else return qmax(k-1,val,t[pre][c],t[pos][c]); } int main() { scanf("%d%d",&n,&m); upnode(23,0,0,T[0]); rep(i,1,n) { int x;scanf("%d",&x); s[i]=s[i-1]^x; upnode(23,s[i],T[i-1],T[i]); }int l,r; while(m--) { scanf("%s",ss); if(ss[0]=='A') { int x;scanf("%d",&x);n++;s[n]=s[n-1]^x; upnode(23,s[n],T[n-1],T[n]); } else { scanf("%d%d%d",&l,&r,&x); int val=x^s[n]; printf("%d ",qmax(23,val,T[l-2],T[r-1])); } } return 0; }