[Luogu 3835]【模板】可持久化平衡树

Description

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

插入x数
删除x数(若有多个相同的数，因只删除一个，如果没有请忽略该操作)
查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数，如不存在输出-2147483647)
求x的后继(后继定义为大于x，且最小的数，如不存在输出2147483647)

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

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

Input

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

接下来每行包含三个正整数，第 $i$ 行记为 $v_i, opt_i, x_i$。

$v_i$表示基于的过去版本号（ $ 0 leq v_i < i$ ），$opt_i$ 表示操作的序号( $ 1 leq opt leq 6 $ )， $x_i$ 表示参与操作的数值

Output

每行包含一个正整数，依次为各个3,4,5,6操作所对应的答案

Sample Input

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

Sample Output

9
1
2
10
3

Hint

数据范围：

对于10%的数据满足： $ 1 leq n leq 10 $

对于30%的数据满足： $ 1 leq n leq 2cdot {10}^2 $

对于50%的数据满足： $ 1 leq n leq 3cdot {10}^3 $

对于80%的数据满足： $ 1 leq n leq {10}^5 $

对于90%的数据满足： $ 1 leq n leq 2cdot {10}^5 $

对于100%的数据满足： $ 1 leq n leq 5cdot {10}^5 $ , $-{10}^9 leq x_i leq {10}^9$

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

样例说明：

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

$[]$
$[9]$
$[3, 9]$
$[9, 10]$
$[3, 9]$
$[9, 10]$
$[2, 9, 10]$
$[2, 9, 10]$
$[2, 10]$
$[2, 10]$
$[3, 9]$

题解

用 $fhq\_treap$ 来实现可持久化。

对于新建的版本，需要更新的点只有 $split$ 和 $merge$ 经过的点。

  1 //It is made by Awson on 2018.1.3
  2 #include <set>
  3 #include <map>
  4 #include <cmath>
  5 #include <ctime>
  6 #include <queue>
  7 #include <stack>
  8 #include <cstdio>
  9 #include <string>
 10 #include <vector>
 11 #include <cstdlib>
 12 #include <cstring>
 13 #include <iostream>
 14 #include <algorithm>
 15 #define LL long long
 16 #define LD long double
 17 #define Max(a, b) ((a) > (b) ? (a) : (b))
 18 #define Min(a, b) ((a) < (b) ? (a) : (b))
 19 using namespace std;
 20 const int N = 5e5;
 21 const int M = N*50;
 22 const int INF = ~0u>>1;
 23 
 24 struct fhq_Treap {
 25     int root[N+5], ch[M+5][2], key[M+5], lev[M+5], size[M+5], tot;
 26     queue<int>mem;
 27     int newnode(int keyy) {
 28     int o;
 29     if (!mem.empty()) o = mem.front(), mem.pop();
 30       else o = ++tot;
 31     ch[o][0] = ch[o][1] = 0, key[o] = keyy, lev[o] = rand(), size[o] = 1;
 32     return o;
 33     }
 34     int cpynode(int r) {
 35     int o;
 36     if (!mem.empty()) o = mem.front(), mem.pop();
 37       else o = ++tot;
 38     ch[o][0] = ch[r][0], ch[o][1] = ch[r][1], key[o] = key[r], lev[o] = lev[r], size[o] = size[r];
 39     return o;
 40     }
 41     void pushup(int o) {
 42     size[o] = size[ch[o][0]]+size[ch[o][1]]+1;
 43     }
 44     void split(int o, int keyy, int &x, int &y) {
 45     if (!o) x = y = 0;
 46     else {
 47         if (key[o] <= keyy) {
 48         x = cpynode(o), split(ch[x][1], keyy, ch[x][1], y);
 49         pushup(x);
 50         }else {
 51         y = cpynode(o), split(ch[y][0], keyy, x, ch[y][0]);
 52         pushup(y);
 53         }
 54     }
 55     }
 56     int merge(int x, int y) {
 57     if (!x || !y) return x+y;
 58     if (lev[x] < lev[y]) {
 59         int r = cpynode(x);
 60         ch[r][1] = merge(ch[r][1], y);
 61         pushup(r); return r;
 62     }else {
 63         int r = cpynode(y);
 64         ch[r][0] = merge(x, ch[r][0]);
 65         pushup(r); return r;
 66     }
 67     }
 68     void insert(int &o, int keyy) {
 69     int r1, r2;
 70     split(o, keyy, r1, r2);
 71     o = merge(merge(r1, newnode(keyy)), r2);
 72     }
 73     void delet(int &o, int keyy) {
 74     int r1, r2, r3;
 75     split(o, keyy-1, r1, r2);
 76     split(r2, keyy, r2, r3);
 77     if (r2) mem.push(r2);
 78     r2 = merge(ch[r2][0], ch[r2][1]);
 79     o = merge(merge(r1, r2), r3);
 80     }
 81     int rank(int &o, int keyy) {
 82     int r1, r2;
 83     split(o, keyy-1, r1, r2);
 84     int ans = size[r1]+1;
 85     o = merge(r1, r2);
 86     return ans;
 87     }
 88     int get_num(int o, int rank) {
 89     if (rank == size[ch[o][0]]+1) return key[o];
 90     if (size[ch[o][0]] >= rank) return get_num(ch[o][0], rank);
 91     return get_num(ch[o][1], rank-(size[ch[o][0]]+1));
 92     }
 93     int get_pre(int &o, int keyy) {
 94     int r1, r2;
 95     split(o, keyy-1, r1, r2);
 96     int r = r1;
 97     while (ch[r][1]) r = ch[r][1];
 98     int ans = key[r];
 99     o = merge(r1, r2);
100     return ans;
101     }
102     int get_nex(int &o, int keyy) {
103     int r1, r2;
104     split(o, keyy, r1, r2);
105     int r = r2;
106     while (ch[r][0]) r = ch[r][0];
107     int ans = key[r];
108     o = merge(r1, r2);
109     return ans;
110     }
111 }T;
112 int n, v, opt, x;
113 
114 void work() {
115     srand(time(0));
116     T.insert(T.root[0], -INF);
117     T.insert(T.root[0], INF);
118     scanf("%d", &n);
119     for (int i = 1; i <= n; i++) {
120     scanf("%d%d%d", &v, &opt, &x);
121     T.root[i] = T.root[v];
122     if (opt == 1) T.insert(T.root[i], x);
123     else if (opt == 2) T.delet(T.root[i], x);
124     else if (opt == 3) printf("%d
", T.rank(T.root[i], x)-1);
125     else if (opt == 4) printf("%d
", T.get_num(T.root[i], x+1));
126     else if (opt == 5) printf("%d
", T.get_pre(T.root[i], x));
127     else printf("%d
", T.get_nex(T.root[i], x));
128     }
129 }
130 int main() {
131     work();
132     return 0;
133 }