[Tyvj 1728]普通平衡树

题目

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
　　1. 插入x数
　　2. 删除x数(若有多个相同的数，因只删除一个)
　　3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
　　4. 查询排名为x的数
　　5. 求x的前驱(前驱定义为小于x，且最大的数)
　　6. 求x的后继(后继定义为大于x，且最小的数)

INPUT

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

OUTPUT

对于操作3,4,5,6每行输出一个数，表示对应答案

SAMPLE

INPUT

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

OUTPUT

106465

84185
492737

解题报告

一道裸的平衡树板子题，也是我的Treap首题，留念

 #include<iostream>
 #include<cstring>
 #include<cstdlib>
 #include<cstdio>
 using namespace std;
 inline int read(){
     int sum(),f();
     char ch(getchar());
     while(ch<''||ch>''){
         if(ch=='-')
             f=-;
         ch=getchar();
     }
     while(ch>=''&&ch<=''){
         sum=sum*+ch-'';
         ch=getchar();
     }
     return sum*f;
 }
 struct node{
     int size,key,v;
     node *ch[];
     node():size(),key(rand()),v(){
         ch[]=ch[]=NULL;
     }
     node(int x):size(),key(rand()),v(x){
         ch[]=ch[]=NULL;
     }
 }*root;
 inline int get_size(node *x){
     if(x==NULL)
         return ;
     return x->size;
 }
 inline void pushup(node *rt){
     rt->size=get_size(rt->ch[])+get_size(rt->ch[])+;
 }
 inline void ro(node *&rt,int d){
     node *tmp(rt->ch[d^]);
     rt->ch[d^]=tmp->ch[d];
     pushup(rt);
     tmp->ch[d]=rt;
     pushup(tmp);
     rt=tmp;
 }
 inline void insert(node *&rt,int x){
     if(!rt){
         rt=new node(x);
         return;
     }
     int d(rt->v>x);
     insert(rt->ch[d^],x);
     pushup(rt);
     if(rt->ch[d^]->key>rt->key)
         ro(rt,d);
 }
 inline void del(node *&rt,int x){
     if(rt->v==x){
         if(rt->ch[]!=NULL&&rt->ch[]!=NULL){
             int d(rt->ch[]->key>rt->ch[]->key);
             ro(rt,d);
             del(rt->ch[d],x);
         }
         else{
             node *tmp=NULL;
             if(rt->ch[]!=NULL)
                 tmp=rt->ch[];
             else
                 tmp=rt->ch[];
             delete rt;
             rt=tmp;
         }
     }
     else{
         int d(rt->v>x);
         del(rt->ch[d^],x);
     }
     if(rt!=NULL)
         pushup(rt);
 }
 inline int rk(int x){
     node *rt(root);
     int ret();
     while(rt){
         if(x>rt->v){
             ret+=get_size(rt->ch[])+;
             rt=rt->ch[];
         }
         else
             rt=rt->ch[];
     }
     return ret;
 }
 inline int kth(int k){
     node *rt(root);
     while(rt){
         if(get_size(rt->ch[])+==k)
             return rt->v;
         if(get_size(rt->ch[])+>k)
             rt=rt->ch[];
         else{
             k-=get_size(rt->ch[])+;
             rt=rt->ch[];
         }
     }
     return ;
 }
 inline int gg(){
     freopen("phs.in","r",stdin);
     freopen("phs.out","w",stdout);
     srand(time(NULL));
     int n(read());
     while(n--){
         int op(read()),x(read());
         if(op==){
             insert(root,x);
             continue;
         }
         if(op==){
             del(root,x);
             continue;
         }
         if(op==){
             printf("%d\n",rk(x)+);
             continue;
         }
         if(op==){
             printf("%d\n",kth(x));
             continue;
         }
         if(op==){
             printf("%d\n",kth(rk(x)));
             continue;
         }
         if(op==){
             printf("%d\n",kth(rk(x+)+));
             continue;
         }
     }
 }
 int k(gg());
 int main(){;}

玄学板子，调的时间比打的时间还长= =
ps：参数类型一定要写对QWQ