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 2\cdot {10}^2 $
对于50%的数据满足： $ 1 \leq n \leq 3\cdot {10}^3 $
对于80%的数据满足： $ 1 \leq n \leq {10}^5 $
对于90%的数据满足： $ 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个版本，各版本的状况依次是：
$[]$
$[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$ 经过的点。
//It is made by Awson on 2018.1.3
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define LD long double
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
const int N = 5e5;
const int M = N*;
const int INF = ~0u>>; struct fhq_Treap {
int root[N+], ch[M+][], key[M+], lev[M+], size[M+], tot;
queue<int>mem;
int newnode(int keyy) {
int o;
if (!mem.empty()) o = mem.front(), mem.pop();
else o = ++tot;
ch[o][] = ch[o][] = , key[o] = keyy, lev[o] = rand(), size[o] = ;
return o;
}
int cpynode(int r) {
int o;
if (!mem.empty()) o = mem.front(), mem.pop();
else o = ++tot;
ch[o][] = ch[r][], ch[o][] = ch[r][], key[o] = key[r], lev[o] = lev[r], size[o] = size[r];
return o;
}
void pushup(int o) {
size[o] = size[ch[o][]]+size[ch[o][]]+;
}
void split(int o, int keyy, int &x, int &y) {
if (!o) x = y = ;
else {
if (key[o] <= keyy) {
x = cpynode(o), split(ch[x][], keyy, ch[x][], y);
pushup(x);
}else {
y = cpynode(o), split(ch[y][], keyy, x, ch[y][]);
pushup(y);
}
}
}
int merge(int x, int y) {
if (!x || !y) return x+y;
if (lev[x] < lev[y]) {
int r = cpynode(x);
ch[r][] = merge(ch[r][], y);
pushup(r); return r;
}else {
int r = cpynode(y);
ch[r][] = merge(x, ch[r][]);
pushup(r); return r;
}
}
void insert(int &o, int keyy) {
int r1, r2;
split(o, keyy, r1, r2);
o = merge(merge(r1, newnode(keyy)), r2);
}
void delet(int &o, int keyy) {
int r1, r2, r3;
split(o, keyy-, r1, r2);
split(r2, keyy, r2, r3);
if (r2) mem.push(r2);
r2 = merge(ch[r2][], ch[r2][]);
o = merge(merge(r1, r2), r3);
}
int rank(int &o, int keyy) {
int r1, r2;
split(o, keyy-, r1, r2);
int ans = size[r1]+;
o = merge(r1, r2);
return ans;
}
int get_num(int o, int rank) {
if (rank == size[ch[o][]]+) return key[o];
if (size[ch[o][]] >= rank) return get_num(ch[o][], rank);
return get_num(ch[o][], rank-(size[ch[o][]]+));
}
int get_pre(int &o, int keyy) {
int r1, r2;
split(o, keyy-, r1, r2);
int r = r1;
while (ch[r][]) r = ch[r][];
int ans = key[r];
o = merge(r1, r2);
return ans;
}
int get_nex(int &o, int keyy) {
int r1, r2;
split(o, keyy, r1, r2);
int r = r2;
while (ch[r][]) r = ch[r][];
int ans = key[r];
o = merge(r1, r2);
return ans;
}
}T;
int n, v, opt, x; void work() {
srand(time());
T.insert(T.root[], -INF);
T.insert(T.root[], INF);
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d%d%d", &v, &opt, &x);
T.root[i] = T.root[v];
if (opt == ) T.insert(T.root[i], x);
else if (opt == ) T.delet(T.root[i], x);
else if (opt == ) printf("%d\n", T.rank(T.root[i], x)-);
else if (opt == ) printf("%d\n", T.get_num(T.root[i], x+));
else if (opt == ) printf("%d\n", T.get_pre(T.root[i], x));
else printf("%d\n", T.get_nex(T.root[i], x));
}
}
int main() {
work();
return ;
}