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

本题为题目 **普通平衡树** 的可持久化加强版。 **数据已经经过强化** **感谢@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即为初始状态，空树）

无

无

【数据范围】 对于 $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]$