不想多说什么了。费空间，也不算太快，唯一的好处就是好写吧。
#include#include const int MAXN=100010<<5,INF=10000000;int n;class Trie{ public: Trie(void) { cnt=1; memset(s,0,sizeof s); } void Insert(int x) { int k=1,p=x+INF; for(int i=30,t;~i;++s[k=s[k].c[t]].size,--i) if(!s[k].c[t=p>>i&1]) s[k].c[t]=++cnt; s[k].v=x; } void Erase(int x) { int k=1,p=x+INF; for(int i=30;~i;--s[k=s[k].c[p>>i&1]].size,--i); } int Rank(int x) { int k=1,p=x+INF,ans=1; for(int i=30,t;~i;--i,k=s[k].c[t]) if(t=p>>i&1) ans+=s[s[k].c[0]].size; return ans; } int Find(int x) { int k=1,ans=0; for(int i=30,t,f;~i;--i,k=s[k].c[t]) if(t=(x>(f=s[s[k].c[0]].size))) x-=f; return s[k].v; } int Pre(int x) { return Find(Rank(x)-1); } int Next(int x) { return Find(Rank(x+1)); } private: int cnt; struct node { int v,size,c[2]; }s[MAXN];}T;int main(int argc,char *argv[]){ freopen("testdata.in","r",stdin); freopen("my.out","w",stdout); scanf("%d",&n); for(int i=1,opt,x;i<=n;++i) { scanf("%d %d",&opt,&x); switch(opt) { case 1: T.Insert(x); break; case 2: T.Erase(x); break; case 3: printf("%d\n",T.Rank(x)); break; case 4: printf("%d\n",T.Find(x)); break; case 5: printf("%d\n",T.Pre(x)); break; case 6: printf("%d\n",T.Next(x)); break; } } fclose(stdin); fclose(stdout); return 0;}
谢谢阅读。