【深基16.例7】普通二叉树(简化版)

题目描述

您需要写一种数据结构,来维护一些数(都是绝对值 $10^9$ 以内的数)的集合,最开始时集合是空的。其中需要提供以下操作,操作次数 $q$ 不超过 $10^4$: 1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。查询数 $x$ 的排名。**注意 $x$ 不一定在集合里**。 2. 查询排名为 $x(x\ge 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

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

输出样例 #1

2
3
1
5