https://vjudge.net/problem/HDU-2852
#include<iostream> #include<cstdio> #include<algorithm> #include<ctime> using namespace std; const int p=100000007; struct treap_node { treap_node *left,*right; int value,cnt,siz;unsigned long long pro; treap_node(treap_node *l,treap_node *r,int v,unsigned long long p) { left=l,right=r,value=v,pro=p;cnt=siz=1; } }; treap_node *Treap; int totle_nodes; unsigned long long get_pro() { return (unsigned long long)rand(); } void re_cal(treap_node *now) { now->siz=now->cnt; if(now->left) now->siz+=now->left->siz; if(now->right) now->siz+=now->right->siz; } treap_node* insert(treap_node *now,int value) { if(!now) return new treap_node(nullptr,nullptr,value,get_pro()); if(value==now->value) return now+0*(now->siz++,now->cnt++); if(value<(now->value)) { now->left=insert(now->left,value); if(now->left->pro<now->pro) { treap_node *final_node=now->left; now->left=now->left->right;re_cal(now); final_node->right=now;re_cal(final_node); return final_node; } re_cal(now);return now; } now->right=insert(now->right,value); if(now->right->pro<now->pro) { treap_node *final_node=now->right; now->right=now->right->left;re_cal(now); final_node->left=now;re_cal(final_node); return final_node; } re_cal(now);return now; } treap_node* del(treap_node *now,int value) { if(!now) return nullptr; if(value==now->value) { if(now->cnt>1) return now+0*(now->cnt--,now->siz--); int type=(now->left?1:0)+(now->right?1:0); treap_node *final_node; switch(type) { case 0: delete now; return nullptr; case 1: final_node=(now->left)?now->left:now->right; delete now; return final_node; case 2: if(now->left->pro<now->right->pro) { final_node=now->left; now->left=now->left->right;re_cal(now); final_node->right=now;re_cal(final_node); final_node->right=del(final_node->right,value); re_cal(final_node);return final_node; }else { final_node=now->right; now->right=now->right->left;re_cal(now); final_node->left=now;re_cal(final_node); final_node->left=del(final_node->left,value); re_cal(final_node);return final_node; } } } if(value<now->value) now->left=del(now->left,value); else now->right=del(now->right,value); re_cal(now);return now; } bool check(treap_node *now,int value) { if(!now) return false; if(value==now->value) return true; if(value<now->value) return check(now->left,value); return check(now->right,value); } void clear_tree(treap_node *now) { if(!now) return; if(now->left) clear_tree(now->left); if(now->right) clear_tree(now->right); delete now; } int get_rank(treap_node *now,int value) { if(!now) return -1; int left_size=(now->left?now->left->siz:0); if(value<now->value) return now->left?get_rank(now->left,value):-1; if(value==now->value) return left_size+1; if(!now->right) return -1; return left_size+(now->cnt)+get_rank(now->right,value); } int get_ele(treap_node *now,int kth) { if(now->left) if(now->left->siz>=kth) return get_ele(now->left,kth); else kth-=now->left->siz; if(kth<=now->cnt) return now->value; if(now->right&&kth-now->cnt<=now->right->siz) return get_ele(now->right,kth-now->cnt);return -1; } void init_all() { clear_tree(Treap);Treap=nullptr; totle_nodes=0; } int main() { //freopen("in.txt","r",stdin); srand((unsigned)time(0)); int Q,e,a,k; while(EOF!=scanf("%d",&Q)) { int oper; init_all();while(Q--) { scanf("%d",&oper); switch(oper) { case 0: scanf("%d",&e); totle_nodes++;Treap=insert(Treap,e); break; case 1: scanf("%d",&e); if(!check(Treap,e)) puts("No Elment!"); else Treap=del(Treap,e),totle_nodes--; break; case 2: scanf("%d %d",&a,&k);a++; Treap=insert(Treap,a);int real_rank=k+get_rank(Treap,a)-1; Treap=del(Treap,a);if(real_rank>totle_nodes) puts("Not Find!"); else printf("%d\n",get_ele(Treap,real_rank)); break; } } } return 0; }