You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

数据已经经过强化

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

题目描述

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

1、 插入 $x$

2、 删除 $x$（若有多个相同的数，应只删除一个，如果没有请忽略该操作）

3、 查询 $x$ 的排名（排名定义为比当前数小的数的个数 $+1$）

4、查询排名为 $x$ 的数

5、 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数，如不存在输出 $-2^{31}+1$ ）

6、求 $x$ 的后继（后继定义为大于 $x$，且最小的数，如不存在输出 $2^{31}-1$ ）

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

每个版本的编号即为操作的序号（版本0即为初始状态，空树）

输入格式

第一行包含一个正整数 $n$ ，表示操作的总数。

接下来 $n$ 行，每行包含三个整数，第 $i$ 行记为 $v_i, \text{opt}_i, x_i$。

$v_i$ 表示基于的过去版本号，$\text{opt}_i$ 表示操作的序号， $x_i$ 表示参与操作的数值

输出格式

每行包含一个整数，依次为各个 $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 \leq n \leq 10$；
对于 $44\%$ 的数据，$1 \leq n \leq 2\times {10}^2$；
对于 $60\%$ 的数据， $1 \leq n \leq 3\times {10}^3$；
对于 $84\%$ 的数据， $1 \leq n \leq {10}^5$；
对于 $92\%$ 的数据， $1 \leq n \leq 2\times {10}^5$；
对于 $100\%$ 的数据， $1 \leq n \leq 5 \times 10^5$ , $|x_i| \leq {10}^9$，$0 \le v_i < i$，$1\le \text{opt} \le 6$。

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

样例说明：

共 $10$ 次操作，$11$ 个版本，各版本的状况依次是：

0. $[]$

1. $[9]$

2. $[3, 9]$

3. $[9, 10]$

4. $[3, 9]$

5. $[9, 10]$

6. $[2, 9, 10]$

7. $[2, 9, 10]$

8. $[2, 10]$

9. $[2, 10]$

10. $[3, 9]$