3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 12204  Solved: 5199

[][][]

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

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

Sample Output

106465

84185

492737

HINT

 

1.n的数据范围：n<=100000

2.每个数的数据范围：[-2e9,2e9]

 

Source

 

1 /*f[i]表示i的父结点  2 ch[i][0]表示i的左儿子  3 ch[i][1]表示i的右儿子  4 key[i]表示i的关键字（即结点i代表的那个数字）  5 cnt[i]表示i结点的关键字出现的次数（相当于权值）  6 size[i]表示包括i的这个子树的大小  7 sz为整棵树的大小  8 root为整棵树的根编号   9 */ 10 //借用某神犇的话 没事就多转转  11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 using namespace std; 16   17 const int maxn=100010; 18 int f[maxn],ch[maxn][2],key[maxn],cnt[maxn],size[maxn],sz,root; 19 int n,opt,num; 20   21 void clean(int x){
    //清空  22     ch[x][0]=ch[x][1]=f[x]=cnt[x]=key[x]=size[x]=0; 23 } 24   25 int get(int x){
    //判断当前点是左还是右  26     return ch[f[x]][1]==x;//?????? 27 } 28   29 void update(int x){
    //更新size值  30     if(x){ 31         size[x]=cnt[x]; 32         if(ch[x][0]) size[x]+=size[ch[x][0]]; 33         if(ch[x][1]) size[x]+=size[ch[x][1]]; 34     } 35     return; 36 } 37   38 void rotate(int x){ 39     int old=f[x]; 40     int oldf=f[old]; 41     int which=get(x); 42     ch[old][which]=ch[x][which^1]; 43     f[ch[old][which]]=old; 44     f[old]=x; 45     ch[x][which^1]=old; 46     f[x]=oldf; 47     if(oldf) ch[oldf][ch[oldf][1]==old]=x; 48     update(old); 49     update(x);  50 } 51   52 void splay(int x){  53     for(int fa;fa=f[x];rotate(x)) 54         if(f[fa]) rotate((get(x)==get(fa)?fa:x)); 55     root=x; 56 } 57   58 int find(int v){
    //查询某数的排名  59     int ans=0; 60     int now=root; 61     while(1){ 62         if(v
          
           1){105         cnt[root]--;106         return;107     }108     if(!ch[root][0]&&!ch[root][1]){109         clean(root);110         root=0;111         return;112     }113     if(!ch[root][0]){114         int oldroot=root;115         root=ch[root][1];116         f[root]=0;117         clean(oldroot);118         return;119     }120     else if(!ch[root][1]){121         int oldroot=root;122         root=ch[root][0];123         f[root]=0;124         clean(oldroot);125         return;126     }127     int leftbig=pre();128     int oldroot=root;129     splay(leftbig);130     f[ch[oldroot][1]]=root;131     ch[root][1]=ch[oldroot][1];132     clean(oldroot);133     update(root);134     return;135 }136  137 void insert(int v){138     if(!root){139         sz++;140         ch[sz][0]=ch[sz][1]=f[sz]=0;141         key[sz]=v;142         cnt[sz]=1;143         size[sz]=1;144         root=sz;145         return;146     }147     int now=root;148     int fa=0;149     while(1){150         if(key[now]==v){151             cnt[now]++;152             update(fa);153             splay(now);154             break;155         }156         fa=now;157         now=ch[now][key[now]
          
         
        
       
      

 

 

存作模板