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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define MAXN (100000+10)

 using namespace std;

 int Father[MAXN];

 int Son[MAXN][];

 int Key[MAXN];//结点代表的数字

 int Cnt[MAXN];//结点代表数字出现次数

 int Size[MAXN];//子树大小（含自身）

 int Root,sz,n,opt,x;

 void Clear(int x){Father[x]=Son[x][]=Son[x][]=Key[x]=Cnt[x]=Size[x]=;}

 void New(int x){Size[++sz]=;Key[sz]=x;Cnt[sz]=;}

 void Update(int x){Size[x]=Cnt[x]+Size[Son[x][]]+Size[Son[x][]];}

 int Get(int x){return x==Son[Father[x]][];}

 int Pre(){int now=Son[Root][];    while (Son[now][]) now=Son[now][];return now;}

 int Next(){    int now=Son[Root][];while (Son[now][]) now=Son[now][];return now;}

 void Rotate(int x)

 {

     int wh=Get(x);

     int fa=Father[x],fafa=Father[fa];

     Son[fa][wh]=Son[x][wh^];

     Father[fa]=x;

     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;

     Son[x][wh^]=fa;

     Father[x]=fafa;

     if (fafa) Son[fafa][Son[fafa][]==fa]=x;

     Update(fa);

     Update(x);

 }

 void Splay(int x)

 {

     for (int fa; fa=Father[x]; Rotate(x))

         if (Father[fa])

             Rotate(Get(fa)==Get(x)?fa:x);

     Root=x;

 }

 int Find(int x)

 {

     int ans=,now=Root;

     while ()

         if (x<Key[now])

             now=Son[now][];

         else

         {

             ans+=Size[Son[now][]];

             if (x==Key[now])

             {

                 Splay(now);

                 return ans+;

             }

             ans+=Cnt[now];

             now=Son[now][];

         }

 }

 int Findx(int x)

 {

     int now=Root;

     while ()

         if (x<=Size[Son[now][]])

             now=Son[now][];

         else

         {

             x-=Size[Son[now][]];

             if (x<=Cnt[now])

             {

                 Splay(now);

                 return Key[now];

             }

             x-=Cnt[now];

             now=Son[now][];

         }

 }

 void Insert(int x)

 {

     if (Root==)

     {

         New(x);

         Root=sz;

         return;

     }

     int now=Root,fa=;

     while ()

     {

         if (x==Key[now])

         {

             Cnt[now]++;

             Update(now);

             Splay(now);

             return;

         }

         fa=now,now=Son[now][Key[now]<x];

         if (now==)

         {

             New(x);

             Father[sz]=fa;

             Son[fa][x>Key[fa]]=sz;

             // Update(fa);

             Splay(sz);

             return;

         }

     }

 }

 void Delete(int x)

 {

     Find(x);

     if (Cnt[Root]>)

     {

         --Cnt[Root];

         Update(Root);

         return;

     }

     if (!Son[Root][] && !Son[Root][])

     {

         Clear(Root);

         Root=;

         return;

     }

     if (!Son[Root][])

     {

         Root=Son[Root][];

         Clear(Father[Root]);

         Father[Root]=;

         return;

     }

     if (!Son[Root][])

     {

         Root=Son[Root][];

         Clear(Father[Root]);

         Father[Root]=;

         return;

     }

     int old=Root;

     Splay(Pre());

     Son[Root][]=Son[old][];

     Father[Son[old][]]=Root;

     Clear(old);

     Update(Root);

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

     {

         scanf("%d%d",&opt,&x);

         if (opt==) Insert(x);

         if (opt==) Delete(x);

         if (opt==) printf("%d\n",Find(x));

         if (opt==) printf("%d\n",Findx(x));

         if (opt==) Insert(x),printf("%d\n",Key[Pre()]),Delete(x);

         if (opt==) Insert(x),printf("%d\n",Key[Next()]),Delete(x);

     }

 }