#P3835. 【模板】可持久化平衡树

    ID: 5020 远端评测题 2000ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>线段树平衡树深度优先搜索,DFS可持久化

【模板】可持久化平衡树

题目背景

本题为题目 普通平衡树 的可持久化加强版。

数据已经经过强化

感谢@Kelin 提供的一组hack数据

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个可重整数集合,其中需要提供以下操作( 对于各个以往的历史版本 ):

1、 插入 xx

2、 删除 xx(若有多个相同的数,应只删除一个,如果没有请忽略该操作

3、 查询 xx 的排名(排名定义为比当前数小的数的个数 +1+1

4、查询排名为 xx 的数

5、 求 xx 的前驱(前驱定义为小于 xx,且最大的数,如不存在输出 231+1-2^{31}+1

6、求 xx 的后继(后继定义为大于 xx,且最小的数,如不存在输出 23112^{31}-1

和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化)

每个版本的编号即为操作的序号(版本0即为初始状态,空树)

输入格式

第一行包含一个正整数 nn ,表示操作的总数。

接下来 nn 行,每行包含三个整数,第 ii 行记为 vi,opti,xiv_i, \text{opt}_i, x_i

viv_i 表示基于的过去版本号,opti\text{opt}_i 表示操作的序号, xix_i 表示参与操作的数值

输出格式

每行包含一个整数,依次为各个 3,4,5,63,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%28\% 的数据,1n10 1 \leq n \leq 10
对于 44%44\% 的数据,1n2×102 1 \leq n \leq 2\times {10}^2
对于 60%60\% 的数据, 1n3×103 1 \leq n \leq 3\times {10}^3
对于 84%84\% 的数据, 1n105 1 \leq n \leq {10}^5
对于 92%92\% 的数据, 1n2×105 1 \leq n \leq 2\times {10}^5
对于 100%100\% 的数据, 1n5×105 1 \leq n \leq 5 \times 10^5 , xi109|x_i| \leq {10}^90vi<i0 \le v_i < i1opt61\le \text{opt} \le 6

经实测,正常常数的可持久化平衡树均可通过,请各位放心

样例说明:

1010 次操作,1111 个版本,各版本的状况依次是:

  1. [][]

  2. [9][9]

  3. [3,9][3, 9]

  4. [9,10][9, 10]

  5. [3,9][3, 9]

  6. [9,10][9, 10]

  7. [2,9,10][2, 9, 10]

  8. [2,9,10][2, 9, 10]

  9. [2,10][2, 10]

  10. [2,10][2, 10]

  11. [3,9][3, 9]