1 int top;
 2 struct SBT {
 3     int L,R,size,key;
 4     void init() {
 5         L=R=0; size=1;
 6     }
 7 }T[MAX];
 8 
 9 void R_Roate(int &t) {   // 右旋转
10     int k = T[t].L;
11     T[t].L=T[k].R;
12     T[k].R=t;
13     T[k].size=T[t].size;
14     T[t].size=T[T[t].R].size+T[T[t].L].size+1   ;
15     t=k;
16     return ;
17 }
18 void L_Roate(int &t) {  //左旋转
19     int k=T[t].R;
20     T[t].R=T[k].L;
21     T[k].L=t;
22     T[k].size=T[t].size;
23     T[t].size=T[T[t].L].size+T[T[t].R].size+1;
24     t=k;
25     return ;
26 }
27 
28 void Maintain(int &t,bool flag) {   //调整
29     if(!flag) {
30         if(T[T[T[t].L].L].size>T[T[t].R].size) {
31             R_Roate(t);
32         }
33         else if(T[T[T[t].L].R].size>T[T[t].R].size) {
34             R_Roate(T[t].L);
35             R_Roate(t);
36         }
37         else return ;
38     }
39     else {
40         if(T[T[T[t].R].R].size>T[T[t].L].size) {
41             L_Roate(t);
42         }
43         else if(T[T[T[t].R].L].size>T[T[t].L].size) {
44             R_Roate(T[t].R);
45             L_Roate(t);
46         }
47         else return ;
48     }
49     Maintain(T[t].L,false);
50     Maintain(T[t].R,true);
51     Maintain(t,false);
52     Maintain(t,true);
53 }
54 
55 void Insert(int &t,int v) {   //插入
56     if(t==0) {
57         t=++top;
58         T[t].init();
59         T[t].key=v;
60     }
61     else {
62         T[t].size++;
63         if(T[t].key>v) Insert(T[t].L,v);
64         else Insert(T[t].R,v);
65         Maintain(t,v>=T[t].key);
66     }
67 }
68 int Pred(int t,int v) {    //小于v的最大的数，没有小于v的数字则返回v.
69     if(t==0) {
70         return v;
71     }
72     if(v>T[t].key) {
73         int res=Pred(T[t].R,v);
74         if(res==v) return T[t].key;
75         return res;
76     }
77     else return Pred(T[t].L,v);
78 }
79 int Succ(int t,int v) {    //返回大于v的最小的数字，全都小于v则返回v.
80     if(t==0) return v;
81     if(v>=T[t].key) return Succ(T[t].R,v);
82     else {
83         int res=Succ(T[t].L,v);
84         if(v==res) return T[t].key;
85         return res;
86     }
87 }
88 
89 int Exist (int t,int v) {
90     if(t==0) return false;
91     if(v<T[t].key) return Exist(T[t].L,v);
92     else if(v==T[t].key) return true;
93     else return Exist(T[t].R,v);
94 }