来自FallDream的博客，未经允许，请勿转载，谢谢。
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
n<=100000
我怎么也没想到省选考了可持久化无旋Treap 妥妥爆10分。
所以临时补一下无旋Treap 指针写起来挺舒服的
#include<iostream> #include<cstdio> #define Size(x) (x?x->sz:0) using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } inline int Ran() { static int x=23333; x^=(x<<13);x^=(x>>17);x^=(x<<5); return x; } struct Treap { Treap *l,*r; int x,k,sz; Treap(){l=r=NULL;} Treap(int key){l=r=NULL;x=key;k=Ran();sz=1;} void update(){sz=Size(l)+Size(r)+1;} }*rt; typedef pair<Treap*,Treap*> D; Treap* Merge(Treap*x,Treap*y) { if(!x) return y; if(!y) return x; if(x->k<y->k) return x->r=Merge(x->r,y),x->update(),x; else return y->l=Merge(x,y->l),y->update(),y; } D Split(Treap*x,int Rk) { if(!x) return D(NULL,NULL); D b; if(Size(x->l)>=Rk) { b=Split(x->l,Rk); x->l=b.second; x->update(); b.second=x; } else { b=Split(x->r,Rk-Size(x->l)-1); x->r=b.first; x->update(); b.first=x; } return b; } int Find(Treap*x,int v) { int sz=Size(x->l)+1; if(sz==v) return x->x; return sz<v?Find(x->r,v-sz):Find(x->l,v); } int GetRk(Treap*x,int v) { if(!x)return 0; return v<=x->x?GetRk(x->l,v):GetRk(x->r,v)+Size(x->l)+1; } void Insert(int v) { int rk=GetRk(rt,v); D a=Split(rt,rk); Treap*N=new Treap(v); N=Merge(a.first,N); rt=Merge(N,a.second); } void Delete(int v) { int Rk=GetRk(rt,v); D a=Split(rt,Rk); D b=Split(a.second,1); rt=Merge(a.first,b.second); } Treap* Ask_Before(Treap*x,int v) { if(!x) return NULL; Treap* a; if(x->x<v) return (a=Ask_Before(x->r,v))?a:x; else return Ask_Before(x->l,v); } Treap* Ask_After(Treap*x,int v) { if(!x) return NULL; Treap* a; if(x->x>v) return (a=Ask_After(x->l,v))?a:x; else return Ask_After(x->r,v); } int main() { for(int n=read();n;--n) { int op=read(),x=read(); if(op==1) Insert(x); if(op==2) Delete(x); if(op==3) printf("%d ",GetRk(rt,x)+1); if(op==4) printf("%d ",Find(rt,x)); if(op==5) printf("%d ",Ask_Before(rt,x)->x); if(op==6) printf("%d ",Ask_After(rt,x)->x); } return 0; }