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]
题解:平衡树裸题,我立志挖个写splay详解博客的坑,鬼知道省选之后会不会退役,反正难填
代码如下:
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 500010
using namespace std; struct Splay
{
int son[N][],fa[N],key[N],cnt[N],size[N],rt,sz,pos;
inline void push(int x)
{
size[x]=size[son[x][]]+size[son[x][]]+cnt[x];
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y],k=(son[y][]==x);
son[z][son[z][]==y]=x;
fa[x]=z;
son[y][!k]=son[x][k];
fa[son[x][k]]=y;
son[x][k]=y;
fa[y]=x;
push(y);
}
inline void splay(int x,int goal)
{
for(;fa[x]!=goal;rotate(x))
{
int y=fa[x],z=fa[y];
if(z!=goal)
{
(son[y][]==x)^(son[z][]==y)?rotate(x):rotate(y);
}
}
push(x);
if(!goal)
{
rt=x;
}
}
inline void find(int x)
{
for(pos=rt;son[pos][x>key[pos]]&&x!=key[pos];pos=son[pos][x>key[pos]]);
splay(pos,);
}
inline void get(int x,int k)
{
find(x);
if(!(key[pos]>x&&k||key[pos]<x&&!k))
{
for(pos=son[pos][k];son[pos][!k];pos=son[pos][!k]);
}
}
inline void insert(int x)
{
int father=;
for(pos=rt;pos&&key[pos]!=x;pos=son[pos][x>key[pos]])
{
father=pos;
}
if(pos)
{
++cnt[pos];
}
else
{
pos=++sz;
son[father][x>key[father]]=pos;
son[pos][]=son[pos][]=;
fa[pos]=father;
key[pos]=x;
cnt[pos]=size[pos]=;
}
splay(pos,);
}
inline void del(int x)
{
get(x,);
int pre=pos;
get(x,);
int next=pos;
splay(pre,);
splay(next,pre);
pos=son[next][];
if(cnt[pos]>)
{
--cnt[pos];
--size[pos];
}
else
{
son[next][]=;
}
push(next);
push(pre);
}
inline void kth(int k)
{
for(pos=rt;;)
{
int y=son[pos][];
if(k>size[y]+cnt[pos])
{
k-=size[y]+cnt[pos];
pos=son[pos][];
}
else
{
if(size[y]<k)
{
return;
}
else
{
pos=y;
}
}
}
}
inline void put_key()
{
printf("%d\n",key[pos]);
}
}splay1; int main()
{
int n,kd,val;
splay1.insert(-1e9);
splay1.insert(1e9);
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&kd,&val);
int x;
switch(kd)
{
case :splay1.insert(val);
break;
case :splay1.del(val);
break;
case :splay1.find(val);
x=splay1.size[splay1.son[splay1.pos][]];
printf("%d\n",x);
break;
case :splay1.kth(val+);
splay1.put_key();
break;
case :splay1.get(val,);
splay1.put_key();
break;
case :splay1.get(val,);
splay1.put_key();
break;
}
}
}