同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1579_普通平衡树

2022-5-16 18:17| 发布者: Hocassian| 查看: 55| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503990683999-Problem List-采集的数据-后羿采集器.html

Pro.ID

1579

Title

普通平衡树

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1579

AC

Submit

Ratio

33.33%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

描述

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 x 数；
删除 x 数（若有多个相同的数，因只删除一个）；
查询 x 数的排名（若有多个相同的数，因输出最小的排名）；
查询排名为 x 的数；
求 x 的前趋（前趋定义为小于 x ，且最大的数）；
求 x 的后继（后继定义为大于 x ，且最小的数）。

输入

多测试用例。

每个测试用例第一行为 n ，表示操作的个数，下面 n 行每行有两个数 opt 和 x ，opt 表示操作的序号（1 ≤ opt ≤ 6 ）。

1 ≤ n ≤ 10⁵ , −10⁷ ≤ x ≤ 10⁷

输出

Description

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 x 数；
删除 x 数（若有多个相同的数，因只删除一个）；
查询 x 数的排名（若有多个相同的数，因输出最小的排名）；
查询排名为 x 的数；
求 x 的前趋（前趋定义为小于 x ，且最大的数）；
求 x 的后继（后继定义为大于 x ，且最小的数）。

Input

多测试用例。

每个测试用例第一行为 n ，表示操作的个数，下面 n 行每行有两个数 opt 和 x ，opt 表示操作的序号（1 ≤ opt ≤ 6 ）。

1 ≤ n ≤ 10⁵ , −10⁷ ≤ x ≤ 10⁷

Output

每个测试用例，对于操作 3、4、5、6 每行输出一个数，表示对应答案。

然后输出一个空行。

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

Author

John

样例输入