题目描述
这是一道模板题，其数据比「普通平衡树」更强。
如未特别说明，以下所有数据均为整数。
维护一个多重集
S
S ，初始为空，有以下几种操作：
把
x
x 加入
S
S
删除
S
S 中的一个
x
x，保证删除的
x
x 一定存在
求
S
S 中第
k
k 小
求
S
S 中有多少个元素小于
x
x
求
S
S 中小于
x
x 的最大数
求
S
S 中大于
x
x 的最小数
操作共
n
n 次。
输入
第一行一个整数
n
n，表示共有
n
n 次操作 。
接下来
n
n 行，每行为以下几种格式之一 ：
0 x，把
x
x 加入
S
S
1 x，删除
S
S 中的一个
x
x，保证删除的数在
S
S 中一定存在
2 k，求
S
S 中第
k
k 小的数，保证要求的数在
S
S 中一定存在
3 x，求
S
S 中有多少个数小于
x
x
4 x，求
S
S 中小于
x
x 的最大数，如果不存在，输出
-1
−1
5 x，求
S
S 中大于
x
x 的最小数，如果不存在，输出
-1
−1
输出
对于每次询问，输出单独一行表示答案。
样例输入
5
0 3
0 4
2 2
1 4
3 3
样例输出
4
0
提示
数据范围与提示
1 \leq n \leq 3 \times 10 ^ 5, 0 \leq x \leq 10 ^ 9
1≤n≤3×105,0≤x≤109
来源/分类
平衡树 数据结构