[BZOJ 3224]普通平衡树
很好,这很interesting。
最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……
还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣!
代码:
/************************************************************** Problem: 3224 User: danihao123 Language: C++ Result: Accepted Time:376 ms Memory:1880 kb ****************************************************************/ #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; struct Node{ Node *ch[2]; int v; int r; int s; int cnt; Node(){ v=s=cnt=0; r=-1; ch[0]=ch[1]=NULL; } Node(int key,Node *lc,Node *rc){ v=key; r=rand(); s=1; cnt=1; ch[0]=lc; ch[1]=rc; } void maintain(){ s=ch[0]->s+ch[1]->s+cnt; } }; struct Treap{ Node *null,*root; Treap(){ null=new Node(); root=null; } void rotate(Node* &o,int d){ Node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d]; k->ch[d]=o; o->maintain(); k->maintain(); o=k; } void insert(Node* &o,int x){ if(o==null){ o=new Node(x,null,null); }else{ if(o->v==x){ o->cnt++; o->s++; }else{ int d=x>(o->v); insert(o->ch[d],x); if(((o->ch[d])->r)>(o->r)) rotate(o,d^1); } } o->maintain(); } void del(Node* &o,int x){ if(o->v==x){ if(o->cnt>1){ o->cnt--; o->s--; }else{ if(o->ch[0]==null){ Node *u=o; o=o->ch[1]; delete u; }else{ if(o->ch[1]==null){ Node *u=o; o=o->ch[0]; delete u; }else{ int d=(o->ch[1]->r)>(o->ch[0]->r); rotate(o,d^1); del(o->ch[d^1],x); } } } }else{ int d=x>(o->v); del(o->ch[d],x); } if(o!=null) o->maintain(); } int kth(Node *o,int k){ if(k<=(o->ch[0]->s)){ return kth(o->ch[0],k); }else{ k-=o->ch[0]->s; if(k<=o->cnt) return o->v; else return kth(o->ch[1],k-(o->cnt)); } } int rank(Node *o,int x){ if(o==null) return 0; if(x<(o->v)){ return rank(o->ch[0],x); }else{ if(x==o->v) return o->ch[0]->s+1; else return o->ch[0]->s+o->cnt+rank(o->ch[1],x); } } int pre(int x){ Node *cur=root; int ans=0; while(cur!=null){ if(cur->v<x){ ans=cur->v; cur=cur->ch[1]; }else{ cur=cur->ch[0]; } } return ans; } int suc(int x){ Node *cur=root; int ans=0; while(cur!=null){ if(cur->v>x){ ans=cur->v; cur=cur->ch[0]; }else{ cur=cur->ch[1]; } } return ans; } }; int main(){ int n; int opt,x; Treap T; scanf("%d",&n); srand(20020601); while(n--){ scanf("%d%d",&opt,&x); if(opt==1){ T.insert(T.root,x); }else{ if(opt==2){ T.del(T.root,x); }else{ if(opt==3){ printf("%d\n",T.rank(T.root,x)); }else{ if(opt==4){ printf("%d\n",T.kth(T.root,x)); }else{ if(opt==5){ printf("%d\n",T.pre(x)); }else{ printf("%d\n",T.suc(x)); } } } } } } return 0; }