题目地址：

https://www.luogu.com.cn/problem/P3835

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

题目描述：
您需要写一种数据结构（可参考题目标题），来维护一个可重整数集合，其中需要提供以下操作（对于各个以往的历史版本）：
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$操作所对应的答案

数据范围：
对于$28\%$的数据，$1\le n\le 10$；
对于$44\%$的数据，$1\le n\le 2\times {10}^2$；
对于$60\%$的数据，$1\le n\le 3\times {10}^3$；
对于$84\%$的数据，$1\le n\le {10}^5$；
对于$92\%$的数据，$1\le n\le 2\times {10}^5$；
对于$100\%$的数据，$1\le n\le 5\times 10^5$ , $|x_i|\le {10}^9$，$0\le v_i<i$，$1\le \text{opt}\le 6$。

需要用FHQ Treap。可持久化平衡树，一般要写成无旋Treap的形式，即FHQ Treap。FHQ Treap参考https://blog.csdn.net/qq_46105170/article/details/118997891。不需要持久化的话，效果如下：
考虑需要持久化的情形。由于需要持久化，我们需要维持当前版本的结构不变，以方便以后来查询。由于FHQ Treap是基于分裂合并来进行所有操作的，所以我们要考虑分裂和合并如何做持久化。分裂的时候，从树根向下走的那条进行分裂的路径，需要另外开新的点，剩余的点用当前版本的点。如下图：

同样是分裂为小于等于$3$和大于$3$的两棵子树，分裂的路径是$6\to 2\to 5\to 3\to 4$，这个路径上小于等于$3$的点和大于$3$的点都copy一份，这样尽量利用了没有改变的部分，从而节省了维护版本需要的空间。而合并的时候，由于合并之前一定是进行了分裂，所以合并的时候合并的“拼接处”和分裂的时候那条链是一样的，所以并不需要新开节点。具体思路与不持久化的情形类似。代码如下：

#include 
#include 
using namespace std;

const int N = 5e5 + 10;
int n, root[N], idx;
int x, y, z;
struct Node {
  int l, r;
  int key, val;
  int sz;
} tr[N * 50];

int newnode(int v) {
  int p = ++idx;
  tr[p].key = v;
  tr[p].val = rand();
  tr[p].sz = 1;
  return p;
}

#define pushup(u) tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1

void split(int p, int v, int &x, int &y) {
  if (!p) {
    x = y = 0;
    return;
  }

  if (tr[p].key <= v) {
    x = ++idx;
    tr[x] = tr[p];
    split(tr[x].r, v, tr[x].r, y);
    pushup(x);
  } else {
    y = ++idx;
    tr[y] = tr[p];
    split(tr[y].l, v, x, tr[y].l);
    pushup(y);
  }
}

int merge(int x, int y) {
  if (!x || !y) return x ^ y;
  if (tr[x].val < tr[y].val) {
    tr[x].r = merge(tr[x].r, y);
    pushup(x);
    return x;
  } else {
    tr[y].l = merge(x, tr[y].l);
    pushup(y);
    return y;
  }
}

void insert(int &root, int v) {
  split(root, v, x, y);
  z = newnode(v);
  root = merge(merge(x, z), y);
}

void remove(int &root, int v) {
  split(root, v, x, z);
  split(x, v - 1, x, y);
  y = merge(tr[y].l, tr[y].r);
  root = merge(merge(x, y), z);
}

int get_rank(int &root, int v) {
  split(root, v - 1, x, y);
  int res = tr[x].sz + 1;
  root = merge(x, y);
  return res;
}

int get_key(int root, int rk) {
  if (rk <= tr[tr[root].l].sz) return get_key(tr[root].l, rk);
  else if (rk > tr[tr[root].l].sz + 1)
    return get_key(tr[root].r, rk - tr[tr[root].l].sz - 1);
  else return tr[root].key;
}

int get_prev(int &root, int v) {
  split(root, v - 1, x, y);
  if (!x) return INT_MIN;
  int res = get_key(x, tr[x].sz);
  root = merge(x, y);
  return res;
}

int get_next(int &root, int v) {
  split(root, v, x, y);
  if (!y) return INT_MAX;
  int res = get_key(y, 1);
  root = merge(x, y);
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int vi, op, x;
    scanf("%d%d%d", &vi, &op, &x);
    root[i] = root[vi];
    if (op == 1) insert(root[i], x);
    else if (op == 2) remove(root[i], x);
    else if (op == 3) printf("%d\n", get_rank(root[i], x));
    else if (op == 4) printf("%d\n", get_key(root[i], x));
    else if (op == 5) printf("%d\n", get_prev(root[i], x));
    else printf("%d\n", get_next(root[i], x));
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

每次操作时间复杂度$O(\log n)$，空间$O(n\log n)$。