3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 14480 Solved: 6275

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]

code

  1 #include<cstdio>
  2 using namespace std;
  3  
  4 const int MAXN = 100010;
  5  
  6 int fa[MAXN],ch[MAXN][2],siz[MAXN],cnt[MAXN],data[MAXN];
  7 /*fa表示父亲，ch表示左儿子和右儿子，siz表示当前节点的大小，cnt表示重复数字多少，data表示存储的数字*/
  8 int tot,root,n;
  9  
 10 int son(int x)
 11 {
 12     return x==ch[fa[x]][1];
 13 }
 14 void pushup(int rt)
 15 {
 16     int l = ch[rt][0], r = ch[rt][1];
 17     siz[rt] = siz[l]+siz[r]+cnt[rt];
 18 }
 19 void rotate(int x)//翻转操作 
 20 {
 21     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
 22     if (z) ch[z][c] = x; else root = x;fa[x] = z;
 23     if (a) fa[a] = y; ch[y][b] = a;
 24     ch[x][!b] = y;fa[y] = x;
 25     pushup(y);
 26     pushup(x);
 27 }
 28 void splay(int x,int rt)
 29 {
 30     while (fa[x]!=rt)
 31     {
 32         int y = fa[x],z = fa[y];
 33         if (z==rt) rotate(x);
 34         else
 35         {
 36             if (son(x)==son(y))
 37             {
 38                 rotate(y);rotate(x);
 39             }
 40             else
 41             {
 42                 rotate(x);rotate(x);
 43             }
 44         }
 45     }
 46 }
 47 void ins(int &rt,int x)//插入操作 
 48 {
 49     if (rt==0)
 50     {
 51         rt = ++tot;
 52         data[tot] = x;
 53         siz[tot] = cnt[tot] = 1;
 54         return ;
 55     }
 56     if (x==data[rt])
 57     {
 58         cnt[rt] ++;
 59         siz[rt] ++;
 60         return ;
 61     }
 62     if (x<data[rt])
 63     {
 64         ins(ch[rt][0],x);
 65         fa[ch[rt][0]] = rt;
 66         pushup(rt);
 67     }
 68     else
 69     {
 70         ins(ch[rt][1],x);
 71         fa[ch[rt][1]] = rt;
 72         pushup(rt);
 73     }
 74 }
 75 int getmn(int rt)
 76 {
 77     int p = rt,ans = -1;
 78     while (p)
 79     {
 80         ans = p;
 81         p = ch[p][0];
 82     }
 83     return ans;
 84 }
 85 void del(int rt,int x)//删除操作 
 86 {
 87     if (data[rt]==x)
 88     {
 89         if (cnt[rt]>1)
 90         {
 91             cnt[rt]--;siz[rt]--;
 92         }
 93         else
 94         {
 95             splay(rt,0);
 96             int p = getmn(ch[rt][1]);
 97             if (p!=-1)
 98             {
 99                 splay(p,rt);
100                 root = p;fa[p] = 0;
101                 ch[p][0] = ch[rt][0];fa[ch[rt][0]] = p;
102                 pushup(p);
103             }
104             else
105             {
106                 root = ch[rt][0];
107                 fa[ch[rt][0]] = 0;
108             }
109         }
110         return ;
111     }
112     if (x<data[rt])
113     {
114         del(ch[rt][0],x);
115         pushup(rt);
116     }
117     else
118     {
119         del(ch[rt][1],x);
120         pushup(rt);
121     }
122 }
123 int getpre(int rt,int x)//找前驱 
124 {
125     int p = rt,ans;
126     while (p)
127     {
128         if (x<=data[p]) p = ch[p][0];
129         else ans = p, p = ch[p][1];
130     }
131     return ans;
132 }
133 int getsuc(int rt,int x)//找后继 
134 {
135     int p = rt,ans;
136     while (p)
137     {
138         if (x>=data[p]) p = ch[p][1];
139         else ans = p, p = ch[p][0];
140     }
141     return ans;
142 }
143 int getk(int rt,int k)//找k的排序 
144 {
145     if (data[rt]==k)
146     {
147         splay(rt,0);
148         if (ch[rt][0]==0) return 1;
149         else return siz[ch[rt][0]]+1;
150     }
151     if (k<data[rt]) return getk(ch[rt][0],k);
152     else return getk(ch[rt][1],k);  
153 }
154 int getkth(int rt,int k)//找第k个数 
155 {
156     int l = ch[rt][0];
157     if (siz[l]+1<=k&&k<=siz[l]+cnt[rt]) return data[rt];
158     if (k<siz[l]+1) return getkth(ch[rt][0],k);
159     if (siz[l]+cnt[rt]<k) return getkth(ch[rt][1],k-(siz[l]+cnt[rt]));
160 }
161 int main()
162 {
163     scanf("%d",&n);
164     while (n--)
165     {
166         int opt,x;
167         scanf("%d%d",&opt,&x);
168         if (opt==1) ins(root,x);
169         if (opt==2) del(root,x);
170         if (opt==3)
171             printf("%d
",getk(root,x));
172         if (opt==4)
173             printf("%d
",getkth(root,x));
174         if (opt==5)
175             printf("%d
",data[getpre(root,x)]);
176         if (opt==6)
177             printf("%d
",data[getsuc(root,x)]);
178     }   
179     return 0;
180 }