二叉搜索树模板

题目描述

你需要维护一个可重集合，初始为空。支持以下 6 种操作：

1. 1 x：插入一个数 x
2. 2 x：删除一个数 x，保证集合中存在至少一个 x
3. 3 x：查询 x 的排名，即小于 x 的数的个数加 1
4. 4 k：查询第 k 小的数，保证 1 <= k <= 当前集合大小
5. 5 x：查询小于 x 的最大数，保证存在
6. 6 x：查询大于 x 的最小数，保证存在

输入格式

第一行一个整数 n，表示操作次数。

接下来 n 行，每行两个整数 op x 或 op k，含义如上。

输出格式

对于每个 op = 3, 4, 5, 6 的操作，输出一行一个整数表示答案。

数据范围

• 1 <= n <= 10^5
• |x| <= 10^9
• 保证所有操作合法：
  • 删除的数一定存在；
  • 第 k 小查询的 k 一定合法；
  • 前驱 / 后继查询保证答案存在。

样例输入

7
1 5
1 3
1 7
3 5
4 2
5 6
6 6

样例输出

2
5
5
7

样例解释

插入 5, 3, 7 后集合为 {3, 5, 7}。

• 查询 3 5：小于 5 的数有 3，排名为 2
• 查询 4 2：第 2 小是 5
• 查询 5 6：小于 6 的最大数是 5
• 查询 6 6：大于 6 的最小数是 7