题意：有编号为1-n的商店 每个商店有一个永久化的商品价值为v
操作1：时间过了一天 第x商店增加了一个价值为val的货物
操作2：该火星人有自己的密码值x 问第L个商店到第R个商店的 当前天-d+1 到 当前天 的所有货物中（包括永久化商品) 异或x的最大值
最大异或值显然是可持久化trie树
一开始永久化的话在一开始更新即可
建立一棵时间线段树 先把火星人扔进时间线段树
然后把操作按照时间进行cdq即可
注意操作要按商店编号排序 因为可持久化更新要求有序性
注意商店编号不一定是连续的 所以用一个序来维护可持久化trie
#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=1e5+10; int t[N<<5][2],T[N],siz[N<<5],ncnt,b[N]; void upnode(int k,int x,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=(x>>k)&1; upnode(k-1,x,t[pre][c],t[pos][c]); } int qmax(int k,int x,int pre,int pos) { if(k<0)return 0; int c=(x>>k)&1; if( siz[t[pos][c^1]-t[pre][c^1]]>0 )return (1<<k)+qmax(k-1,x,t[pre][c^1],t[pos][c^1]); else return qmax(k-1,x,t[pre][c],t[pos][c]); } vector<int>node[N<<2]; int n,m,ans[N]; void addnode(int x,int L,int R,int l,int r,int pos) { if(L>R)return ; if(L<=l&&r<=R){node[pos].push_back(x);return;} int m=(l+r)>>1; if(L<=m)addnode(x,L,R,l,m,pos<<1); if(R>m)addnode(x,L,R,m+1,r,pos<<1|1); } struct marspeo{int L, R, s, t, x;}peo[N]; struct upp{int t,x,val;}up[N],s1[N],s2[N]; int cnt1,cnt0; void calc(int L,int R,int pos) { int nn=0;ncnt=0; rep(i,L,R) { nn++;b[nn]=up[i].x; upnode(20,up[i].val,T[nn-1],T[nn]); } for(auto v:node[pos]) { int l=lower_bound(b+1,b+1+nn,peo[v].L)-b; int r=upper_bound(b+1,b+1+nn,peo[v].R)-b-1; int temp=qmax(20,peo[v].x,T[l-1],T[r]); ans[v]=max(ans[v],temp); } } void cdq(int L,int R,int l,int r,int pos)//L R 为操作数 { if(L>R)return ; calc(L,R,pos); if(l==r)return ; int temp1=0,temp2=0,mid=(l+r)>>1; rep(i,L,R) if(up[i].t<=mid)s1[++temp1]=up[i]; else s2[++temp2]=up[i]; rep(i,1,temp1)up[i+L-1]=s1[i]; rep(i,1,temp2)up[i+L+temp1-1]=s2[i]; cdq(L,L+temp1-1, l,mid,pos<<1); cdq(L+temp1,R, mid+1,r,pos<<1|1); } int main() { scanf("%d%d",&n,&m);int x,l,r,op,d; rep(i,1,n)scanf("%d",&x),upnode(20,x,T[i-1],T[i]); while(m--) { scanf("%d",&op); if(!op){scanf("%d%d",&l,&r);cnt0++;up[cnt0]=(upp){cnt0,l,r};} else { scanf("%d%d%d%d",&l,&r,&x,&d); peo[++cnt1]=(marspeo){l,r,max(1,cnt0-d+1),cnt0,x}; ans[cnt1]=qmax(20,x,T[l-1],T[r]); } } rep(i,1,cnt1)addnode(i,peo[i].s,peo[i].t,1,cnt0,1); sort(up+1,up+1+cnt0,[](upp a,upp b){return a.x<b.x;}); cdq(1,cnt0,1,cnt0,1); rep(i,1,cnt1)printf("%d ",ans[i]); return 0; }