【模板】可持久化平衡树

题目背景

本题为题目 **普通平衡树** 的可持久化加强版。 **数据已经经过强化** **感谢@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$ 操作所对应的答案

输入输出样例

输入样例 #1

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

输出样例 #1

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]$