# [模板] 替罪羊树与Treap

## 替罪羊树

### 数据储存与更新

struct Node{
int son[2];
int key; //键值
int siz; //有效节点数
int tot; //总节点数
int cnt; //键值出现次数

Node(){key = siz = tot = son[0] = son[1] = cnt = 0;}
};

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

Node node[MAXN];
int root, now;

inline void update(int root){
node[root].siz = node[lson(root)].siz + node[rson(root)].siz + node[root].cnt;
node[root].tot = node[lson(root)].tot + node[rson(root)].tot + node[root].cnt;
}


### 判断是否失衡

inline bool check(int root){
if(node[lson(root)].tot > node[root].tot * aplha + 3 || node[rson(root)].tot > node[root].tot * aplha + 3)
return true;
return false;
}


### 重构

inline void search(int root, vector <int> &vec){
if(!root)
return;

search(lson(root), vec);

if(node[root].cnt)
vec.push_back(root);

search(rson(root), vec);
}

inline int divide(vector <int> &vec, int l, int r){
if(l > r)
return 0;

int mid = (l + r) >> 1;

int pos = vec[mid];

lson(pos) = divide(vec, l, mid-1);
rson(pos) = divide(vec, mid+1, r);

update(pos);

return pos;
}

inline void rebuild(int& root){
vector <int> vec;
vec.clear();

search(root, vec);
root = divide(vec, 0, vec.size() - 1);
}


### 插入

int _null = 0;
int* null = &_null;

inline int* _insert(int& root, int key){
if(!root){
root = newnode(key);
return null;
}else{

node[root].siz++;
node[root].tot++;

if(node[root].key == key){
node[root].cnt++;
return null;
}else{
int* pos = _insert(node[root].son[key > node[root].key], key);

if(check(root)){
pos = &root;
}

return pos;
}
}
}

inline void insert(int key){
int* pos = _insert(root, key);

if(*pos)
rebuild(*pos);
}


### 删除

inline void _delete(int root, int key){
int pos = root;

while(true){
node[pos].siz--;

if(key < node[pos].key){
pos = lson(pos);
continue;
}

if(node[pos].key == key){
node[pos].cnt--;
return;
}

pos = rson(pos);
}
}

inline void Delete(int key){
_delete(root, key);

if(node[root].siz < node[root].tot * aplha + 3)
rebuild(root);
}


### 排名与第 $k$ 大

inline int find(int key){
int ans = 0;
int pos = root;

while(true){
if(key < node[pos].key){
pos = lson(pos);
continue;
}

ans += node[lson(pos)].siz;

if(node[pos].key == key){
return ans + 1;
}

ans += node[pos].cnt;
pos = rson(pos);
}
}

inline int rank(int x){
int pos = root;

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

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

if(x <= node[pos].cnt)
return node[pos].key;

x -= node[pos].cnt;
pos = rson(pos);
}
}


### 前驱与后继

inline int pre(int key){
insert(key);
int p = rank(find(key) - 1);
Delete(key);

return p;
}

inline int next(int key){
insert(key+1);
int id = find(key+1);
Delete(key+1);

int p = rank(id);
return p;
}


## Treap

$Treap = Tree + Heap$，树堆，是通过随机附加域来保证子树的平衡的。对于每一个节点都赋给它一个随机的 $priority$ 值，使得它是一棵以 $key$ 为主键的二叉查找树的同时，还是一棵以 $priority$ 为主键的堆。

$Treap$ 的常数小，实现也简单，但是因为当 $key$ 和 $priority$ 给定时，树的形态也就唯一确定了，无法实现更多的复杂功能。

### 数据储存与更新

int tree[MAXN][2], siz[MAXN], cnt[MAXN];
int val[MAXN], rd[MAXN];
int tot;

inline void update(int root){
siz[root] = siz[tree[root][0]] + siz[tree[root][1]] + cnt[root];
}


### 旋转

inline void rotate(int &root, int path){
//path = 0 时左儿子旋上来，path = 1 时右儿子旋上来
int son = tree[root][path];

tree[root][path] = tree[son][path^1];
tree[son][path^1] = root;

update(root);
update(son);

root = son;
}


### 插入

inline void insert(int &root, int k){
if(!root){
root = ++tot;
cnt[root] = siz[root] = 1;
val[root] = k;
rd[root] = rand();
return;
}

siz[root]++;

if(val[root] == k){
cnt[root]++;
return;
}

int tmp = val[root] < k;

insert(tree[root][tmp], k);

if(rd[root] > rd[tree[root][tmp]])
rotate(root, tmp);
}


### 删除

• 没有左儿子右儿子
• 有左儿子或有右儿子
• 左右儿子都有

inline void Delete(int &root, int k){
if(!root)
return;

if(val[root] == k){
if(cnt[root] > 1){
cnt[root]--;
siz[root]--;
return;
}

int path = val[tree[root][0]] > val[tree[root][1]];

if(tree[root][0] == 0 || tree[root][1] == 0)
root = tree[root][0] + tree[root][1];
else{
rotate(root, path);
Delete(root, k);
}
}else{
siz[root]--;
Delete(tree[root][val[root] < k], k);
}
}



### 前驱与后继

inline int pre(int root, int k){
if(!root)
return -INF;

if(val[root] >= k)
return pre(tree[root][0], k);

return max(pre(tree[root][1], k), val[root]);
}

inline int next(int root, int k){
if(!root)
return INF;

if(val[root] <= k)
return next(tree[root][1], k);

return min(next(tree[root][0], k), val[root]);
}


## 完整模板

Luogu 3369 – 普通平衡树

### 替罪羊树

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

using namespace std;

namespace Scapegoat{

struct Node{
int son[2];
int key, siz, tot;
int cnt;

Node(){key = siz = tot = son[0] = son[1] = cnt = 0;}
};

const long double aplha = 0.75;
const int MAXN = 200000 + 10;
const int INF = 0x3f3f3f3f;

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

Node node[MAXN];
int root, now;

int _null = 0;
int* null = &_null;

inline void update(int root){
node[root].siz = node[lson(root)].siz + node[rson(root)].siz + node[root].cnt;
node[root].tot = node[lson(root)].tot + node[rson(root)].tot + node[root].cnt;
}

inline int newnode(int key){
++now;

node[now].siz = node[now].tot = node[now].cnt = 1;
node[now].key = key;
return now;
}

inline bool check(int root){
if(node[lson(root)].tot > node[root].tot * aplha + 3 || node[rson(root)].tot > node[root].tot * aplha + 3)
return true;
return false;
}

inline void search(int root, vector <int> &vec){
if(!root)
return;

search(lson(root), vec);

if(node[root].cnt)
vec.push_back(root);

search(rson(root), vec);
}

inline int divide(vector <int> &vec, int l, int r){
if(l > r)
return 0;

int mid = (l + r) >> 1;

int pos = vec[mid];

lson(pos) = divide(vec, l, mid-1);
rson(pos) = divide(vec, mid+1, r);

update(pos);

return pos;
}

inline void rebuild(int& root){
vector <int> vec;
vec.clear();

search(root, vec);
root = divide(vec, 0, vec.size() - 1);
}

inline int* _insert(int& root, int key){
if(!root){
root = newnode(key);
return null;
}else{

node[root].siz++;
node[root].tot++;

if(node[root].key == key){
node[root].cnt++;
return null;
}else{
int* pos = _insert(node[root].son[key > node[root].key], key);

if(check(root)){
pos = &root;
}

return pos;
}
}
}

inline void _delete(int root, int key){
int pos = root;

while(true){
node[pos].siz--;

if(key < node[pos].key){
pos = lson(pos);
continue;
}

if(node[pos].key == key){
node[pos].cnt--;
return;
}

pos = rson(pos);
}
}

inline void insert(int key){
int* pos = _insert(root, key);

if(*pos)
rebuild(*pos);
}

inline void Delete(int key){
_delete(root, key);

if(node[root].siz < node[root].tot * aplha + 3)
rebuild(root);
}

inline int find(int key){
int ans = 0;
int pos = root;

while(true){
if(key < node[pos].key){
pos = lson(pos);
continue;
}

ans += node[lson(pos)].siz;

if(node[pos].key == key){
return ans + 1;
}

ans += node[pos].cnt;
pos = rson(pos);
}
}

inline int rank(int x){
int pos = root;

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

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

if(x <= node[pos].cnt)
return node[pos].key;

x -= node[pos].cnt;
pos = rson(pos);
}
}

inline int pre(int key){
insert(key);
int p = rank(find(key) - 1);
Delete(key);

return p;
}

inline int next(int key){
insert(key+1);
int id = find(key+1);
Delete(key+1);

int p = rank(id);
return p;
}

#undef lson
#undef rson
};

int x = 0;
int p = 1;

char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return p ? x : (-x);
}

int n;

int main(){

#ifdef DEBUG
freopen("testdata.in", "r", stdin);
freopen("testdata.out", "w", stdout);
#endif

for(int i=0; i<n; i++){
int op,id;

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


### Treap

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

using namespace std;
const int MAXN = 200000 + 10;
const int INF = 0x3f3f3f3f;

namespace Treap{
int tree[MAXN][2], siz[MAXN], cnt[MAXN];
int val[MAXN], rd[MAXN];
int tot;

inline void update(int root){
siz[root] = siz[tree[root][0]] + siz[tree[root][1]] + cnt[root];
}

inline void rotate(int &root, int path){
int son = tree[root][path];

tree[root][path] = tree[son][path^1];
tree[son][path^1] = root;

update(root);
update(son);

root = son;
}

inline void insert(int &root, int k){
if(!root){
root = ++tot;
cnt[root] = siz[root] = 1;
val[root] = k;
rd[root] = rand();
return;
}

siz[root]++;

if(val[root] == k){
cnt[root]++;
return;
}

int tmp = val[root] < k;

insert(tree[root][tmp], k);

if(rd[root] > rd[tree[root][tmp]])
rotate(root, tmp);
}

inline int find(int root, int k){
if(!root)
return 0;

if(val[root] == k)
return siz[tree[root][0]] + 1;

if(val[root] > k)
return find(tree[root][0], k);

return find(tree[root][1], k) + siz[tree[root][0]] + cnt[root];
}

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

while(true){
if(k <= siz[tree[pos][0]])
pos = tree[pos][0];
else if(k > siz[tree[pos][0]] + cnt[pos]){
k -= siz[tree[pos][0]];
k -= cnt[pos];
pos = tree[pos][1];
}else
return val[pos];
}
}

inline int pre(int root, int k){
if(!root)
return -INF;

if(val[root] >= k)
return pre(tree[root][0], k);

return max(pre(tree[root][1], k), val[root]);
}

inline int next(int root, int k){
if(!root)
return INF;

if(val[root] <= k)
return next(tree[root][1], k);

return min(next(tree[root][0], k), val[root]);
}

inline void Delete(int &root, int k){
if(!root)
return;

if(val[root] == k){
if(cnt[root] > 1){
cnt[root]--;
siz[root]--;
return;
}

int path = val[tree[root][0]] > val[tree[root][1]];

if(tree[root][0] == 0 || tree[root][1] == 0)
root = tree[root][0] + tree[root][1];
else{
rotate(root, path);
Delete(root, k);
}
}else{
siz[root]--;
Delete(tree[root][val[root] < k], k);
}
}
}

int main(){
srand(time(NULL));

int n, root = 0;
scanf("%d",&n);

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

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