题目背景
本题为题目 普通平衡树 的可持久化加强版。
数据已经经过强化
感谢@Kelin 提供的一组hack数据
题目描述
您需要写一种数据结构(可参考题目标题),来维护一个可重整数集合,其中需要提供以下操作( 对于各个以往的历史版本 ):
1、 插入 x
2、 删除 x(若有多个相同的数,应只删除一个,如果没有请忽略该操作)
3、 查询 x 的排名(排名定义为比当前数小的数的个数 +1)
4、查询排名为 x 的数
5、 求 x 的前驱(前驱定义为小于 x,且最大的数,如不存在输出 −231+1 )
6、求 x 的后继(后继定义为大于 x,且最小的数,如不存在输出 231−1 )
和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化)
每个版本的编号即为操作的序号(版本0即为初始状态,空树)
输入格式
第一行包含一个正整数 n ,表示操作的总数。
接下来 n 行,每行包含三个整数,第 i 行记为 vi,opti,xi。
vi 表示基于的过去版本号,opti 表示操作的序号, xi 表示参与操作的数值
输出格式
每行包含一个整数,依次为各个 3,4,5,6 操作所对应的答案
10
0 1 9
1 1 3
1 1 10
2 4 2
3 3 9
3 1 2
6 4 1
6 2 9
8 6 3
4 5 8
9
1
2
10
3
提示
【数据范围】
对于 28% 的数据,1≤n≤10;
对于 44% 的数据,1≤n≤2×102;
对于 60% 的数据, 1≤n≤3×103;
对于 84% 的数据, 1≤n≤105;
对于 92% 的数据, 1≤n≤2×105;
对于 100% 的数据, 1≤n≤5×105 , ∣xi∣≤109,0≤vi<i,1≤opt≤6。
经实测,正常常数的可持久化平衡树均可通过,请各位放心
样例说明:
共 10 次操作,11 个版本,各版本的状况依次是:
-
[]
-
[9]
-
[3,9]
-
[9,10]
-
[3,9]
-
[9,10]
-
[2,9,10]
-
[2,9,10]
-
[2,10]
-
[2,10]
-
[3,9]