# [模板] FHQ Treap 与可持久化平衡树

### 引言

TreapSplay 是两种常用的平衡树，它们都通过旋转来保证树的平衡，从而使得内粗查询的复杂度为均摊 $O(\log n)$

### Split

inline void split(int root, int k, int &x, int &y){
if(!root){
x = y = 0;
return;
}

if(node[root].val <= k){
x = root;
split(rson(root), k, rson(x), y);
}else{
y = root;
split(lson(root), k, x, lson(y));
}

update(root);
}


### Merge

inline void merge(int &root, int x, int y){
if(x == 0 || y == 0){
root = x + y;
return;
}

if(node[x].rd < node[y].rd){
root = x;
merge(rson(x), rson(x), y);
}else{
root = y;
merge(lson(y), x, lson(y));
}

update(root);
}


### 插入

inline int newnode(int x){
node[++tot].siz = 1;
node[tot].val = x;
node[tot].rd = Random::rand(INT_MAX);
lson(tot) = rson(tot) = 0;

}

inline void insert(int val){
int x = 0, y = 0;
int nnode = newnode(val);

split(root, val, x, y);
merge(x, x, nnode);
merge(root, x, y);
}


### 删除

inline void Delete(int val){
int x = 0, y = 0, z = 0;

split(root, val, x, y);
split(x, val-1, x, z);

merge(z, lson(z), rson(z));
merge(x, x, z);
merge(root, x, y);
}


### 查询第 $k$ 大

inline int rank(int root, int k){
int pos = root;

while(true){
if(node[lson(pos)].siz >= k){
pos = lson(pos);
continue;
}

k -= node[lson(pos)].siz;

if(k <= 1){
return node[pos].val;
}

k -= 1;

pos = rson(pos);
}
}


### 查询排名

inline int find(int val){
int x = 0, y = 0;

split(root, val - 1, x, y);
int tmp = node[x].siz + 1;
merge(root, x, y);

return tmp;
}


### 查询前驱

inline int Pre(int val){
int x = 0, y = 0;
split(root, val - 1, x, y);
int tmp = rank(x, node[x].siz);
merge(root, x, y);

return tmp;

}


### 查询后继

inline int Next(int val){
int x = 0, y = 0;
split(root, val, x, y);
int tmp = rank(y, 1);
merge(root, x, y);
return tmp;
}


### 完整模板

// https://www.luogu.org/problemnew/show/P3369
// Luogu 3369 普通平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;

namespace Random{
long long seed;

inline void srand(int n){
seed = n;
}

inline long long rand(int n){
return seed = (seed * 20020905 % n) + 1;
}
}

using Random::rand;

namespace Treap{

struct Node{
int son[2];
int val, siz, rd;
};

Node node[MAXN];

int tot = 0;
int root = 0;

#define lson(x) node[x].son[0]
#define rson(x) node[x].son[1]

inline void update(int x){
node[x].siz = node[lson(x)].siz + node[rson(x)].siz + 1;
}

inline void merge(int &root, int x, int y){
if(x == 0 || y == 0){
root = x + y;
return;
}

if(node[x].rd < node[y].rd){
root = x;
merge(rson(x), rson(x), y);
}else{
root = y;
merge(lson(y), x, lson(y));
}

update(root);
}

inline void split(int root, int k, int &x, int &y){
if(!root){
x = y = 0;
return;
}

if(node[root].val <= k){
x = root;
split(rson(root), k, rson(x), y);
}else{
y = root;
split(lson(root), k, x, lson(y));
}

update(root);
}

inline int newnode(int x){
node[++tot].siz = 1;
node[tot].val = x;
node[tot].rd = Random::rand(INT_MAX);
lson(tot) = rson(tot) = 0;

}

inline void insert(int val){
int x = 0, y = 0;
int nnode = newnode(val);

split(root, val, x, y);
merge(x, x, nnode);
merge(root, x, y);
}

inline void Delete(int val){
int x = 0, y = 0, z = 0;

split(root, val, x, y);
split(x, val-1, x, z);

merge(z, lson(z), rson(z));
merge(x, x, z);
merge(root, x, y);
}

inline int rank(int root, int k){
int pos = root;

while(true){
if(node[lson(pos)].siz >= k){
pos = lson(pos);
continue;
}

k -= node[lson(pos)].siz;

if(k <= 1){
return node[pos].val;
}

k -= 1;

pos = rson(pos);
}
}

inline int find(int val){
int x = 0, y = 0;

split(root, val - 1, x, y);
int tmp = node[x].siz + 1;
merge(root, x, y);

return tmp;
}

inline int Pre(int val){
int x = 0, y = 0;
split(root, val - 1, x, y);
int tmp = rank(x, node[x].siz);
merge(root, x, y);

return tmp;

}

inline int Next(int val){
int x = 0, y = 0;
split(root, val, x, y);
int tmp = rank(y, 1);
merge(root, x, y);
return tmp;
}

#undef lson
#undef rson

}

int main(){
Random::srand(19260817);

int n;
scanf("%d",&n);

for(int i=0; i<n; i++){
int op,id;
scanf("%d%d",&op,&id);

if(op==1)
Treap::insert(id);
else if(op==2)
Treap::Delete(id);
else if(op==3)
printf("%d\n",Treap::find(id));
else if(op==4)
printf("%d\n",Treap::rank(Treap::root, id));
else if(op==5){
printf("%d\n",Treap::Pre(id));
}else{
printf("%d\n",Treap::Next(id));
}
}
return 0;
}


### 可持久化

FHQ Treap 的持久化只需要在 Split 过程中，基于原树复制一个一样的节点，再进行操作

inline int copynode(int root){
node[++tot] = node[root];
}

inline void split(int oldroot, int k, int &x, int &y){
if(!oldroot){
x = y = 0;
return;
}

int root = copynode(oldroot);

if(node[root].val <= k){
x = root;
split(rson(root), k, rson(root), y);
}else{
y = root;
split(lson(root), k, x, lson(y));
}

update(root);
}


### 可持久化平衡树模板

// https://www.luogu.org/problemnew/show/P3835
// Luogu 3835 可持久化平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>

using namespace std;
const int MAXN = 500000 + 10;

namespace Random{
long long seed;

inline void srand(long long n){
seed = n;
}

inline int rand(){
return seed = (seed * 20020905 % INT_MAX) + 1;
}
}

namespace Treap{
struct Node{
int son[2];
int val, siz, rd;
};

Node node[MAXN << 5];
int tot;

#define lson(x) node[x].son[0]
#define rson(x) node[x].son[1]

inline void update(int x){
node[x].siz = node[lson(x)].siz + node[rson(x)].siz + 1;
}

inline int newnode(int key){
node[++tot].val = key;
node[tot].rd = Random::rand();
node[tot].siz = 1;

}

inline int copynode(int root){
node[++tot] = node[root];
}

inline void split(int oldroot, int k, int &x, int &y){
if(!oldroot){
x = y = 0;
return;
}

int root = copynode(oldroot);

if(node[root].val <= k){
x = root;
split(rson(root), k, rson(root), y);
}else{
y = root;
split(lson(root), k, x, lson(y));
}

update(root);
}

inline void merge(int &root, int x, int y){
if(x == 0 || y == 0){
root = x + y;
return;
}

if(node[x].rd < node[y].rd){
root = x;
merge(rson(x), rson(x), y);
}else{
root = y;
merge(lson(y), x, lson(y));
}

update(root);
}

inline void insert(int& root, int val){
int nnode = newnode(val);
int x = 0, y = 0;

split(root, val, x, y);
merge(x, x, nnode);
merge(root, x, y);
}

inline void Delete(int& root, int val){
int x = 0, y = 0, z = 0;

split(root, val, x, y);
split(x, val - 1, x, z);
merge(z, lson(z), rson(z));
merge(x, x, z);
merge(root, x, y);
}

inline int find(int& root, int val){
int x = 0, y = 0;

split(root, val-1, x, y);
int tmp = node[x].siz + 1;
merge(root, x, y);

return tmp;
}

inline int rank(int& root, int val){
int pos = root;

while(pos){
if(node[lson(pos)].siz >= val){
pos = lson(pos);
continue;
}

val -= node[lson(pos)].siz;

if(val <= 1){
return node[pos].val;
}

val -= 1;
pos = rson(pos);
}
}

inline int Pre(int& root, int val){
int x = 0, y = 0;

split(root, val - 1, x, y);
int tmp = rank(x, node[x].siz);
merge(root, x, y);

return tmp;
}

inline int Next(int& root, int val){
int x = 0, y = 0;

split(root, val, x, y);
int tmp = rank(y, 1);
merge(root, x, y);

return tmp;
}

#undef lson
#undef rson
}

int root[MAXN];

int main(){
Random::srand(19260817);

int n;
scanf("%d",&n);

Treap::insert(root[0], 2147483647);
Treap::insert(root[0], -2147483647);

for(int i=1; i<=n; i++){
int old,op,id;
scanf("%d%d%d",&old, &op,&id);

root[i] = root[old];

if(op==1)
Treap::insert(root[i], id);
else if(op==2)
Treap::Delete(root[i], id);
else if(op==3)
printf("%d\n",Treap::find(root[i], id) - 1);
else if(op==4)
printf("%d\n",Treap::rank(root[i], id + 1));
else if(op==5){
printf("%d\n",Treap::Pre(root[i], id));
}else{
printf("%d\n",Treap::Next(root[i], id));
}
}
return 0;
}