5432: P5076 【深基16.例7】普通二叉树（简化版）

题目描述

您需要写一种数据结构，来维护一些数（都是绝对值 10⁹ 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 q 不超过 10⁴：

• 操作 1：定义数 x 的排名为集合中小于 x 的数的个数 +1。查询数 x 的排名。注意 x 不一定在集合里。
• 操作 2：查询排名为 x（x ≥ 1）的数。保证集合里至少有 x 个数。
• 操作 3：求 x 的前驱（前驱定义为小于 x，且最大的数）。若不存在则输出 -2147483647。
• 操作 4：求 x 的后继（后继定义为大于 x，且最小的数）。若不存在则输出 2147483647。
• 操作 5：插入一个数 x，本题的数据保证插入前 x 不在集合中。

保证执行 1, 3, 4 操作时，集合中有至少一个元素。

输入格式

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

接下来 q 行，每行两个整数 op, x，分别表示操作序号以及操作的参数 x。

输出格式

输出有若干行。对于操作 1, 2, 3, 4，输出一个整数，表示该操作的结果。

输入输出样例 #1

输入 #1

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

输出 #1

2
3
1
5

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

2
3
1
5