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
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
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);
}
}