Description
给定一个初始时为空的整数序列（元素由1开始标号）以及一些询问：
类型1：在数组后面就加入数字x。
类型2：在区间L…R中找到y，最大化（x xor y）。
类型3：删除数组最后K个元素。
类型4：在区间L…R中，统计小于等于x的元素个数。
类型5：在区间L…R中，找到第k小的数。
Input
输入数据第一行为一个整数q，表示询问个数，接下来q行，每行一条询问 对应题目描述。
类型1的询问格式为“1 x”。
类型2的询问格式为“2 L R x”。
类型3的询问格式为“3 k”。
类型4的询问格式为“4 L R x”。
类型5的询问格式为“5 L R k”。
Output
对于每个2、4、5询问输出一行对应答案
用二进制可持久化trie维护前i个数即可
事实上trie和退化为点树的线段树没有本质区别，两者在大部分操作上是可以相通的
trie可以支持查询第k小值，小于x的数的个数以及其它所有线段树的操作，同时支持通常线段树不支持的查询xor指定数的最大值
#include<cstdio> #include<algorithm> #include<cstring> inline int input(){ int x=0,c=getchar(),f=1; while(c>57||c<48){ if(c=='-')f=-1; c=getchar(); } while(c>47&&c<58)x=x*10+c-48,c=getchar(); return x*f; } const int N=520050; int q,rt[N],ap=1; int lc[N*20],rc[N*20],sz[N*20],pp=1; inline int kmin(int r,int l,int k){ int L=0,R=1<<20,M; int s=sz[lc[r]]-sz[lc[l]]; do{ M=L+R>>1; if(s<k){ r=rc[r];l=rc[l]; L=M; s+=sz[lc[r]]-sz[lc[l]]; }else{ r=lc[r];l=lc[l]; R=M; s-=sz[rc[r]]-sz[rc[l]]; } }while(L+1<R); return L; } int less(int r,int l,int x,int L=0,int R=1<<20){ if(x>=R-1)return sz[r]-sz[l]; int M=L+R>>1; if(x<M)return less(lc[r],lc[l],x,L,M); return sz[lc[r]]-sz[lc[l]]+less(rc[r],rc[l],x,M,R); } inline int xins(int x,int w){ int u=pp++,r=u; sz[u]=sz[w]+1; for(int i=1<<19;i;i>>=1){ if(x&i){ lc[u]=lc[w]; u=rc[u]=pp++; w=rc[w]; sz[u]=sz[w]+1; }else{ rc[u]=rc[w]; u=lc[u]=pp++; w=lc[w]; sz[u]=sz[w]+1; } } return r; } inline int xmax(int r,int l,int y){ int x=0; for(int i=1<<19;i;i>>=1){ if(y&i){ if(sz[lc[r]]!=sz[lc[l]])x|=i,r=lc[r],l=lc[l]; else r=rc[r],l=rc[l]; }else{ if(sz[rc[r]]!=sz[rc[l]])x|=i,r=rc[r],l=rc[l]; else r=lc[r],l=lc[l]; } } return x^y; } int main(){ q=input(); for(int i=0;i<q;i++){ switch(input()){ case 1:{ rt[ap]=xins(input(),rt[ap-1]); ap++; break; } case 2:{ int l=input(),r=input(),x=input(); printf("%d ",xmax(rt[r],rt[l-1],x)); break; } case 3:{ int k=input(); ap-=k; for(register int i=rt[ap];i<pp;++i)lc[i]=rc[i]=sz[i]=0; pp=rt[ap]; break; } case 4:{ int l=input(),r=input(),x=input(); printf("%d ",less(rt[r],rt[l-1],x)); break; } case 5:{ int l=input(),r=input(),x=input(); printf("%d ",kmin(rt[r],rt[l-1],x)); break; } } } return 0; }