BZOJ3224:普通平衡树(Splay)

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]

Solution

模板

Code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #define MAXN (100000+10)
  5 using namespace std;
  6 int Father[MAXN];
  7 int Son[MAXN][2];
  8 int Key[MAXN];//结点代表的数字
  9 int Cnt[MAXN];//结点代表数字出现次数
 10 int Size[MAXN];//子树大小（含自身）
 11 int Root,sz,n,opt,x;
 12 
 13 void Clear(int x){Father[x]=Son[x][0]=Son[x][1]=Key[x]=Cnt[x]=Size[x]=0;}
 14 void New(int x){Size[++sz]=1;Key[sz]=x;Cnt[sz]=1;}
 15 void Update(int x){Size[x]=Cnt[x]+Size[Son[x][0]]+Size[Son[x][1]];}
 16 int Get(int x){return x==Son[Father[x]][1];}
 17 int Pre(){int now=Son[Root][0];    while (Son[now][1]) now=Son[now][1];return now;}
 18 int Next(){    int now=Son[Root][1];while (Son[now][0]) now=Son[now][0];return now;}
 19 
 20 void Rotate(int x)
 21 {
 22     int wh=Get(x);
 23     int fa=Father[x],fafa=Father[fa];
 24     Son[fa][wh]=Son[x][wh^1];
 25     Father[fa]=x;
 26     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
 27     Son[x][wh^1]=fa;
 28     Father[x]=fafa;
 29     if (fafa) Son[fafa][Son[fafa][1]==fa]=x;
 30     Update(fa);
 31     Update(x);
 32 }
 33 
 34 void Splay(int x)
 35 {
 36     for (int fa; fa=Father[x]; Rotate(x))
 37         if (Father[fa])
 38             Rotate(Get(fa)==Get(x)?fa:x);
 39     Root=x;
 40 }
 41 
 42 int Find(int x)
 43 {
 44     int ans=0,now=Root;
 45     while (1)
 46         if (x<Key[now])
 47             now=Son[now][0];
 48         else
 49         {
 50             ans+=Size[Son[now][0]];
 51             if (x==Key[now])
 52             {
 53                 Splay(now);
 54                 return ans+1;
 55             }
 56             ans+=Cnt[now];
 57             now=Son[now][1];
 58         }
 59 }
 60 
 61 int Findx(int x)
 62 {
 63     int now=Root;
 64     while (1)
 65         if (x<=Size[Son[now][0]])
 66             now=Son[now][0];
 67         else
 68         {
 69             x-=Size[Son[now][0]];
 70             if (x<=Cnt[now])
 71             {
 72                 Splay(now);
 73                 return Key[now];
 74             }
 75             x-=Cnt[now];
 76             now=Son[now][1];
 77         }
 78 }
 79 
 80 void Insert(int x)
 81 {
 82     if (Root==0)
 83     {
 84         New(x);
 85         Root=sz;
 86         return;
 87     }
 88     int now=Root,fa=0;
 89     while (1)
 90     {
 91         if (x==Key[now])
 92         {
 93             Cnt[now]++;
 94             Update(now);
 95             Splay(now);
 96             return;
 97         }
 98         fa=now,now=Son[now][Key[now]<x];
 99         if (now==0)
100         {
101             New(x);
102             Father[sz]=fa;
103             Son[fa][x>Key[fa]]=sz;
104             // Update(fa);
105             Splay(sz);
106             return;
107         }
108     }
109 }
110 
111 void Delete(int x)
112 {
113     Find(x);
114     if (Cnt[Root]>1)
115     {
116         --Cnt[Root];
117         Update(Root);
118         return;
119     }
120     if (!Son[Root][0] && !Son[Root][1])
121     {
122         Clear(Root);
123         Root=0;
124         return;
125     }
126     if (!Son[Root][1])
127     {
128         Root=Son[Root][0];
129         Clear(Father[Root]);
130         Father[Root]=0;
131         return;
132     }
133     if (!Son[Root][0])
134     {
135         Root=Son[Root][1];
136         Clear(Father[Root]);
137         Father[Root]=0;
138         return;
139     }
140     int old=Root;
141     Splay(Pre());
142     Son[Root][1]=Son[old][1];
143     Father[Son[old][1]]=Root;
144     Clear(old);
145     Update(Root);
146 }
147 
148 int main()
149 {
150     scanf("%d",&n);
151     for (int i=1; i<=n; ++i)
152     {
153         scanf("%d%d",&opt,&x);
154         if (opt==1) Insert(x);
155         if (opt==2) Delete(x);
156         if (opt==3) printf("%d
",Find(x));
157         if (opt==4) printf("%d
",Findx(x));
158         if (opt==5) Insert(x),printf("%d
",Key[Pre()]),Delete(x);
159         if (opt==6) Insert(x),printf("%d
",Key[Next()]),Delete(x);
160     }
161 }