中文题题意我就不说了
解析: 可持久化Trie的模板题，详见注释
代码
#include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; const int maxbit=19; const int maxn=10500005; int tr[500002]; struct PerTrie { int id; int next[maxn][2],num[maxn]; void init(){ id=next[0][0]=next[0][1]=num[0]=0; }//初始化 int f(int x,int i){ return (x>>i)&1; } //判断x的第i位为0或1 void Insert(int& rt,int pre,int x,int pos) //插入 { rt=++id; next[rt][0]=next[pre][0]; //赋等 next[rt][1]=next[pre][1]; num[rt]=num[pre]+1; //数量加1 if(pos==-1) return; int d=f(x,pos); Insert(next[rt][d],next[pre][d],x,pos-1); } int MaxXor(int l,int r,int x) { int ret=0; for(int i=maxbit;i>=0;i--) { int d=f(x,i); int a=next[l][d^1],b=next[r][d^1]; if(num[b]-num[a]>0) ret|=(1<<i),l=a,r=b; //判断是否存在 else l=next[l][d],r=next[r][d]; } return ret; } int MinNum(int l,int r,int x) { int ret=0; for(int i=maxbit;i>=0;i--) { int d=f(x,i); if(d) ret+=num[next[r][0]]-num[next[l][0]]; //比它小的加上 l=next[l][d]; r=next[r][d]; } ret+=num[r]-num[l]; //<=要加上它,<的话就不用了 return ret; } int Kth(int l,int r,int k) { int ret=0; for(int i=maxbit;i>=0;i--) { int t=num[next[r][0]]-num[next[l][0]]; if(t>=k) l=next[l][0],r=next[r][0]; //足够 else ret|=(1<<i),l=next[l][1],r=next[r][1],k-=t; } return ret; } }PT; int main() { int Q; scanf("%d",&Q); int type,l,r,x,cnt=0; tr[0]=0; PT.init(); while(Q--) { scanf("%d",&type); if(type==1) { scanf("%d",&x); ++cnt; PT.Insert(tr[cnt],tr[cnt-1],x,maxbit); //插入新的值 } else if(type==2) { scanf("%d%d%d",&l,&r,&x); printf("%d ",PT.MaxXor(tr[l-1],tr[r],x)^x); } else if(type==3) { scanf("%d",&x); cnt-=x; } else if(type==4) { scanf("%d%d%d",&l,&r,&x); printf("%d ",PT.MinNum(tr[l-1],tr[r],x)); } else { scanf("%d%d%d",&l,&r,&x); printf("%d ",PT.Kth(tr[l-1],tr[r],x)); } } return 0; }