TYVJ 1728 普通平衡树

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]

没有大意

没有解析

直接平衡树模板

  1 /*
  2 Welcome Hacking
  3 Wish You High Rating
  4 */
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<ctime>
  9 #include<cstdlib>
 10 #include<algorithm>
 11 #include<cmath>
 12 #include<string>
 13 using namespace std;
 14 int read(){
 15     int xx=0,ff=1;char ch=getchar();
 16     while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
 17     while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
 18     return xx*ff;
 19 }
 20 const int maxn=100010,maxlongint=(1LL<<31)-1;
 21 int cnt,root;
 22 struct SPLAY{
 23     int v,sum,ch[2],weight,fa;
 24     inline void clear()
 25     {v=sum=weight=0,ch[0]=ch[1]=fa=0;}
 26     void init(int val)
 27     {clear();sum=weight=1,v=val;}
 28 }T[maxn];
 29 bool which(const int&x)
 30 {return T[T[x].fa].ch[1]==x;}
 31 inline void push_up(const int&x)
 32 {T[x].sum=T[T[x].ch[0]].sum+T[T[x].ch[1]].sum+T[x].weight;}
 33 void relink(int x,int y,int tt)
 34 {T[x].ch[tt]=y,T[y].fa=x;}
 35 inline void rotate(int x){
 36     int y=T[x].fa,ffa=T[y].fa,tt=which(x),ttt=which(y);
 37     relink(ffa,x,ttt);
 38     relink(y,T[x].ch[tt^1],tt);
 39     relink(x,y,tt^1);
 40     push_up(y);
 41 }
 42 void splay(int x,int tar){
 43     while(T[x].fa!=tar){
 44         if(T[T[x].fa].fa==tar){
 45             rotate(x);
 46             break;
 47         }
 48         else if(which(x)==which(T[x].fa)){
 49             rotate(T[x].fa);
 50             rotate(x);
 51         }
 52         else{
 53             rotate(x);
 54             rotate(x);
 55         }
 56     }
 57     push_up(x);
 58     if(!tar)
 59         root=x;
 60 }
 61 int get_rank(int x,int val){
 62     if(val==T[x].v)
 63         return 1+T[T[x].ch[0]].sum;
 64     if(val<T[x].v)
 65         return get_rank(T[x].ch[0],val);
 66     return get_rank(T[x].ch[1],val)+T[x].weight+T[T[x].ch[0]].sum;
 67 }
 68 int find_rank(int x,int rk){
 69     if(rk>T[T[x].ch[0]].sum&&rk<=T[T[x].ch[0]].sum+T[x].weight)
 70         return T[x].v;
 71     if(rk<=T[T[x].ch[0]].sum)
 72         return find_rank(T[x].ch[0],rk);
 73     return find_rank(T[x].ch[1],rk-T[T[x].ch[0]].sum-T[x].weight);
 74 }
 75 int find_element(int x,int val){
 76     if(val==T[x].v)
 77         return x;
 78     if(val<T[x].v)
 79         return find_element(T[x].ch[0],val);
 80     return find_element(T[x].ch[1],val);
 81 }
 82 int prev_val(int x,int u,int val){
 83     if(!x)
 84         return u;
 85     if(val>T[x].v)
 86         return prev_val(T[x].ch[1],x,val);
 87     return prev_val(T[x].ch[0],u,val);
 88 }
 89 int next_val(int x,int u,int val){
 90     if(!x)
 91         return u;
 92     if(val<T[x].v)
 93         return next_val(T[x].ch[0],x,val);
 94     return next_val(T[x].ch[1],u,val);
 95 }
 96 void insert(int val){
 97     int x=prev_val(root,0,val),y=next_val(root,0,val);
 98     splay(x,0);
 99     splay(y,x);
100     int z=T[y].ch[0];
101     if(!z){
102         z=++cnt;
103         T[z].init(val);
104         T[y].ch[0]=z;
105         T[z].fa=y;
106     }
107     else{
108         T[z].weight++;
109         T[z].sum++;
110     }
111     push_up(y);
112     push_up(x);
113 }
114 void del(int val){
115     int x=prev_val(root,0,val),y=next_val(root,0,val);
116     splay(x,0);
117     splay(y,x);
118     int z=T[y].ch[0];
119     T[z].weight--;
120     T[z].sum--;
121     if(!T[z].weight){
122         T[z].clear();
123         T[y].ch[0]=0;
124     }
125     push_up(y);
126     push_up(x);
127 }
128 int main(){
129     //freopen("in.txt","r",stdin);
130     //freopen("out2","w",stdout);
131     cnt=2;
132     root=1;
133     T[1].init(maxlongint);
134     T[2].init(-maxlongint);
135     T[1].ch[0]=2;
136     T[2].fa=1;
137     push_up(1);
138     for(int N=read();N;N--){
139         int opt=read(),t=read();
140         switch(opt){
141             case 1:insert(t);break;
142             case 2:del(t);break;
143             case 3:printf("%d
",get_rank(root,t)-1);break;
144             case 4:printf("%d
",find_rank(root,t+1));break;
145             case 5:printf("%d
",T[prev_val(root,0,t)].v);break;
146             case 6:printf("%d
",T[next_val(root,0,t)].v);break;
147         }
148     }
149     return 0;
150 }

View Code