裸的treap
#include<stdio.h> #include<algorithm> #include<stdlib.h> #include<cstring> #include<iostream> #include<string> #include<cmath> #include<vector> #include<queue> #include<map> #include<iterator> #include<stack> using namespace std; #define ll __int64 #define MAXN 500010 #define inf 2000000007 struct node { struct node *ch[2]; int sz,key,num,pri; }; typedef node * tree; node base[MAXN],nil; tree root,null,top; void Init() { top=base; root=null=&nil; null->ch[0]=null->ch[1]=null; null->key=null->pri=null->num=2147483647; null->sz=0; } inline int random() { static int seed=703; return seed=int(seed *48271ll %2147483647); } inline tree newnode(int num,int key) { top->num=num; top->key=key; top->pri=random(); top->sz=1; top->ch[0]=top->ch[1]=null; return top++; } void Rotate(tree &x,bool d) { tree y = x->ch[!d]; x->ch[!d]=y->ch[d]; y->ch[d]=x; x->sz=x->ch[0]->sz+1+x->ch[1]->sz; y->sz=y->ch[0]->sz+1+y->ch[1]->sz; x=y; } void Insert(tree &t,int num,int key) { if(t==null) t=newnode(num,key); else { bool d=key>t->key; Insert(t->ch[d],num,key); (t->sz)++; if(t->pri<t->ch[d]->pri) Rotate(t,!d); } } void Delete(tree &t,int key) { if(t->key!=key) { Delete(t->ch[key>t->key],key); (t->sz)--; } else if(t->ch[0]==null) t=t->ch[1]; else if(t->ch[1]==null) t=t->ch[0]; else { bool d=t->ch[0]->pri<t->ch[1]->pri; Rotate(t,d); Delete(t->ch[d],key); } } tree select(int k) //第k个 { tree t=root; int tmp; for(;;) { tmp=t->ch[0]->sz+1; if(k==tmp) return t; else if(k>tmp) { k-=tmp; t=t->ch[1]; } else t=t->ch[0]; } } int cnt; int main() { Init(); int ty; cnt=0; while(scanf("%d",&ty)!=EOF) { if(ty==0) break; if(ty==1) { int num,key; scanf("%d%d",&num,&key); Insert(root,num,key); cnt++; } else if(ty==2) { if(cnt>0) { tree a=select(cnt); int b=a->key; //printf("%d ",b); Delete(root,b); printf("%d ",a->num); cnt--; } else printf("0 "); } else { if(cnt>0) { tree a=select(1); int b=a->key; Delete(root,b); printf("%d ",a->num); cnt--; } else printf("0 "); } } return 0; }