【模板】可持久化平衡树

题目背景

本题为题目 **普通平衡树** 的可持久化加强版。 **数据已经经过强化** **感谢@Kelin 提供的一组hack数据**

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(**对于各个以往的历史版本**): 1. 插入x数 2. 删除x数(若有多个相同的数,因只删除一个,**如果没有请忽略该操作**) 3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x,且最大的数,**如不存在输出-2147483647**) 6. 求x的后继(后继定义为大于x,且最小的数,**如不存在输出2147483647**) **和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化)** 每个版本的编号即为操作的序号(版本0即为初始状态,空树)

输入输出格式

输入格式


第一行包含一个正整数N,表示操作的总数。 接下来每行包含三个整数,第 $i$ 行记为 $v_i, opt_i, x_i$。 $v_i$表示基于的过去版本号( $ 0 \leq v_i < i$ ),$opt_i$ 表示操作的序号( $ 1 \leq opt \leq 6 $ ), $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\cdot {10}^2 $ 对于60%的数据满足: $ 1 \leq n \leq 3\cdot {10}^3 $ 对于84%的数据满足: $ 1 \leq n \leq {10}^5 $ 对于92%的数据满足: $ 1 \leq n \leq 2\cdot {10}^5 $ 对于100%的数据满足: $ 1 \leq n \leq 5\cdot {10}^5 $ , $-{10}^9 \leq x_i \leq {10}^9$ **经实测,正常常数的可持久化平衡树均可通过,请各位放心** 样例说明: 共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]$