Treap:
#include#include using namespace std;#define INF 0x7fffffff#define ha 19260817#define N 100100inline int rand(){ static int seed=ha; return seed=(int)seed*482711LL%INF;}struct node{ node *ch[2]; int siz,val,key,cnt; inline node(){ ch[0]=ch[1]=NULL; siz=cnt=0; } inline node(int k,int r):key(k),val(r){} inline void update(){ siz=ch[0]->siz+ch[1]->siz+cnt; }};node *root,*null;struct Treap{ inline void init(){ root=null=new node[N]; null->ch[0]=null->ch[1]=null; } inline void rot(node* &u,int op){ node* v=u->ch[op^1]; u->ch[op^1]=v->ch[op]; v->ch[op]=u; u->update(); (u=v)->update(); } void insert(node* &u,int k){ if(!u || u==null){ u=new node(k,rand()); u->siz=u->cnt=1; u->ch[0]=u->ch[1]=null; return ; } if(u->key==k) u->cnt++; else{ int op=k>u->key; insert(u->ch[op],k); if(u->val>u->ch[op]->val) rot(u,op^1); } u->update(); } void erase(node* &u,int k){ if(u==null) return ; if(u->key==k){ if(u->cnt>1) u->cnt--; else if(u->ch[0]==null) u=u->ch[1]; else if(u->ch[1]==null) u=u->ch[0]; else{ int op=u->ch[0]->val>u->ch[1]->val; rot(u,op); erase(u->ch[op],k); } } else erase(u->ch[k>u->key],k); u->update(); } inline int qrnk(int val){ int rnk=1; node* u=root; for(;u!=null;){ if(val key) u=u->ch[0]; else if(val>u->key){ rnk+=u->ch[0]->siz+u->cnt; u=u->ch[1]; } else return rnk+u->ch[0]->siz; } return rnk; } inline int qkey(int rnk){ node* u=root; for(;u!=null;){ if(rnk<=u->ch[0]->siz) u=u->ch[0]; else if(rnk>u->ch[0]->siz+u->cnt){ rnk-=u->ch[0]->siz+u->cnt; u=u->ch[1]; } else return u->key; } return 0; } inline int qpre(int val){ int pre; node* u=root; for(;u!=null;){ if(val>u->key){ pre=u->key; u=u->ch[1]; } else u=u->ch[0]; } return pre; } inline int qsuc(int val){ int suc; node* u=root; for(;u!=null;){ if(val key){ suc=u->key; u=u->ch[0]; } else u=u->ch[1]; } return suc; }} tr;int n,op,x;int main(){ scanf("%d",&n); tr.init(); for(int i=1;i<=n;i++){ scanf("%d%d",&op,&x); switch(op){ case 1:tr.insert(root,x);break; case 2:tr.erase(root,x);break; case 3:printf("%d\n",tr.qrnk(x));break; case 4:printf("%d\n",tr.qkey(x));break; case 5:printf("%d\n",tr.qpre(x));break; case 6:printf("%d\n",tr.qsuc(x));break; } } return 0;}