题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=3224
题目大意：
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
思路：
splay：http://www.cnblogs.com/BCOI/p/9010229.html
treap：https://www.cnblogs.com/BCOI/p/9072444.html
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
#define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Mem(a) memset(a, 0, sizeof(a))
#define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
#define MID(l, r) ((l) + ((r) - (l)) / 2)
#define lson ((o)<<1)
#define rson ((o)<<1|1)
#pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} typedef long long ll;
const int maxn = + ;
const int MOD = ;//const引用更快，宏定义也更快
const int INF = 1e9 + ;
const double eps = 1e-; struct node
{
int fa;//记录父节点
int ch[];//ch[0]表示左儿子 ch[1]表示右儿子
int val;//节点权值
int Size;//记录节点子树大小(包括该节点)
int cnt;//记录同样权值的元素个数
int mark;//记录反转区间标记(普通平衡树不用)
}t[maxn];
int root = ;//根节点
int cnt = ;//当前节点数目
bool get(int x)//判断一个节点是左节点还是右节点
{
return t[t[x].fa].ch[] == x;//右节点返回1 左节点返回0
}
void up(int x)//重新统计节点x的size
{
t[x].Size = t[t[x].ch[]].Size + t[t[x].ch[]].Size + t[x].cnt;
}
void Rotate(int x)//节点x与父节点旋转
{
int fa = t[x].fa, gfa = t[fa].fa;
int d1 = get(x), d2 = get(fa);//加上d1 d2均表示左儿子
t[fa].ch[d1] = t[x].ch[d1 ^ ]; t[t[x].ch[d1 ^ ]].fa = fa;//父节点的左儿子设置成左儿子的右儿子(双向设置)
t[gfa].ch[d2] = x; t[x].fa = gfa;//祖父节点的左儿子设置成父节点的左儿子(双向)
t[fa].fa = x; t[x].ch[d1^] = fa;//左儿子的右儿子设置成父节点(双向)
up(fa); up(x);
}
void splay(int x, int goal)//x旋转到goal下面
{
while(t[x].fa != goal)
{
int fa = t[x].fa, gfa = t[fa].fa;
int d1 = get(x), d2 = get(fa);
if(gfa != goal)
{
if(d1 == d2)Rotate(fa);//同侧，先旋父节点(双旋)
else Rotate(x);//异侧 直接选
}
Rotate(x);//再向上旋一次
}
if(goal == )root = x;
}
void Insert(int val)
{
int node = root, fa = ;
while(node && t[node].val != val)
fa = node, node = t[node].ch[t[node].val < val];
if(node)t[node].cnt++;//节点存在
else
{
node = ++cnt;
if(fa)t[fa].ch[t[fa].val < val] = node;
t[node].fa = fa;
t[node].Size = t[node].cnt = ;
t[node].val = val;
}
splay(node, );//将新节点旋到根来维护splay的子树
}
int kth(int k)//查询第k大的数
{
int node = root;
while()
{
int son = t[node].ch[];
if(k <= t[son].Size)node = son;
else if(k > t[son].Size + t[node].cnt)
{
k -= t[son].Size + t[node].cnt;
node = t[node].ch[];
}
else return t[node].val;
}
}
int Find(int val)//直接调用Find(INF)或者调用Find(-INF)可以得到最大值和最小值编号
{
int node = root;
while(t[node].val != val && t[node].ch[t[node].val < val])
node = t[node].ch[t[node].val < val];
return node;
}
int get_rank(int val)//查询一个数的排名
{
splay(Find(val), );
return t[t[root].ch[]].Size + ;
}
int get_pre(int val, int kind)//kind = 0 查询前驱 kind = 1查询后继
{
splay(Find(val), );
int node = root;
if(t[node].val < val && kind == )return node;
if(t[node].val > val && kind == )return node;//根节点就是前驱/后继的情况
node = t[node].ch[kind];
while(t[node].ch[kind ^ ])node = t[node].ch[kind ^ ];//否则在子树中寻找最值
return node;//返回的是编号 具体的值调用需要用t[node].val
}
void delet(int val)
{
int last = get_pre(val, );//由于此处查询了前驱和后缀 可能会查询到最小值的前驱或者最大值的后缀
int next = get_pre(val, );//必须事先加入INF 和-INF 不然会出错
splay(last, );
splay(next, last);
if(t[t[next].ch[]].cnt > )
{
t[t[next].ch[]].cnt--;
splay(t[next].ch[], );
}
else t[next].ch[] = ;
}
int main()
{
int n, x, y;
Insert(-INF);
Insert(INF);
scanf("%d", &n);
while(n--)
{
scanf("%d%d", &x, &y);
if(x == )Insert(y);
if(x == )delet(y);
if(x == )printf("%d\n", get_rank(y)- );//排名减一是因为要减去负无穷这个数
if(x == )printf("%d\n", kth(y + ));//排名是y+1 因为加上负无穷这个数
if(x == )printf("%d\n", t[get_pre(y, )].val);
if(x == )printf("%d\n", t[get_pre(y, )].val);
}
return ;
}