fhq_Treap——模板整理

2019-04-14 15:25发布

站内文章 / 模拟电子
11957 0 910
好写，而且能可持久化。 #include #include #include using namespace std; struct node{ int key,fix,size; node* ch[2]; node(int tkey=2e+9+5,node* son=NULL){ key=tkey; fix=(rand()<<16)+rand(); size=1; ch[0]=ch[1]=son; } void maintain(){ size=ch[0]->size+ch[1]->size+1; } } nil, *null=&nil, *root=null; typedef node* P_node; void null_init(){ null->fix=-1e+9; null->size=0; null->ch[0]=null->ch[1]=null; } P_node Merge(P_node p1,P_node p2){ if(p1==null||p2==null) return p1==null?p2:p1; if(p1->fix>p2->fix){ p1->ch[1]=Merge(p1->ch[1],p2); p1->maintain(); return p1; } else{ p2->ch[0]=Merge(p1,p2->ch[0]); p2->maintain(); return p2; } } void Split(P_node p,int val,P_node &Left,P_node &Right){ // (-oo,val] (val,+oo) if(p==null){ Left=Right=null; return; } if(p->key<=val) Left=p, Split(p->ch[1],val,p->ch[1],Right); else Right=p, Split(p->ch[0],val,Left,p->ch[0]); p->maintain(); } void Insert(int tkey){ P_node Left,Right; Split(root,tkey-1,Left,Right); root=Merge(Left,Merge(new node(tkey,null),Right)); } void Erase(int tkey){ P_node Left,Right,mid; Split(root,tkey-1,Left,Right); Split(Right,tkey,mid,Right); root=Merge(Left,Merge(Merge(mid->ch[0],mid->ch[1]),Right)); } int Kth(P_node p,int k){ if(p->ch[0]->size==k-1) return p->key; if(p->ch[0]->size>=k) return Kth(p->ch[0],k); return Kth(p->ch[1],k-p->ch[0]->size-1); } int get_edge(P_node p,int k){ while(p->ch[k]!=null) p=p->ch[k]; return p->key; } int n; int main(){ freopen("fhq_treap.in","r",stdin); freopen("fhq_treap.out","w",stdout); null_init(); srand(233); root=Merge(new node(-(2e+9+5),null),new node(2e+9+5,null)); scanf("%d",&n); while(n--){ int pd,x; P_node Left,Right; scanf("%d%d",&pd,&x); if(pd==1) Insert(x); else if(pd==2) Erase(x); else if(pd==3){ Split(root,x-1,Left,Right); printf("%d ",Left->size+1-1); root=Merge(Left,Right); } else if(pd==4){ x++; printf("%d ",Kth(root,x)); } else if(pd==5){ Split(root,x-1,Left,Right); printf("%d ",get_edge(Left,1)); root=Merge(Left,Right); } else if(pd==6){ Split(root,x,Left,Right); printf("%d ",get_edge(Right,0)); root=Merge(Left,Right); } } return 0; }

热门文章