参考1: https://www.acwing.com/solution/content/20092/
参考2: 平衡树详解:treap,spaly…
<关于为什么要用随机性来维护treap堆的性质>:
因为当序列为有序序列如:1 2 3 4 5;
那么BST就会退化为一条链:
2 4
/ \ / \
1 3 5
这样搜索就会很爆炸,因为rand的随机性我们可以以大根堆的形式维护每个节点的rand使得树的期望高度为log(n) 而不至于退化为一条链,从而可以实现以二分的形式去进行修改查询等一系列操作
//trep(平衡树) = BST(二叉搜索树) + heap(堆)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
struct node
{
int l, r;//左儿子 || 右儿子
int cnt, size; //key数值的个数 || size = p.l.size + p.r.size + p.cnt
int key, val;//key:数值,维护key的BST; p.l.key < p.key < p.r.key || val随机数产生来维护树的大根堆:p.val > p.l.val && p.val > p.r.val 来使得树的结构更加随机
}tr[N];
int root, idx;
//子节点信息更新父节点信息
void pushup(int p)
{
//父节点的size = 左儿子size + 右儿子size + 父节点的cnt
tr[p].size = tr[tr[p].l].size + tr[p].cnt + tr[tr[p].r].size;
}
//创建新节点,默认创建为叶子结点
int get_node(int key)
{
tr[++idx].key = key;
tr[idx].size = 1;
tr[idx].cnt = 1;
tr[idx].val = rand();
return idx;
}
//左旋和右旋都是不改变树的中序排列,而将目标节点下移使得节点变为叶子结点,从而实现删除
//zig,zag,insert,remove因为要改变p所以传参要传 &p
void zig(int &p)//右旋
{
int q = tr[p].l;
tr[p].l = tr[q].r;
tr[q].r = p;
p = q;
pushup(tr[p].r), pushup(p);//先更新p.r再更新p
}
void zag(int &p)//左旋
{
int q = tr[p].r;
tr[p].r = tr[q].l;
tr[q].l = p;
p = q;
pushup(tr[p].l), pushup(p);
}
//初始建立两个哨兵:-INF INF 来处理边界问题
void build()
{
//1号点为-INF, 一号点的右儿子为2号点-INF
root = get_node(-INF), get_node(INF);
tr[1].r = 2;
pushup(root);//更新1号节点的信息
if(tr[1].val < tr[2].val) zag(root);//维护父节点val与两个儿子的val来维护树的大根堆结构
}
void insert(int &p, int key)
{
//没有该节点就创建出来
if(!p) p = get_node(key);
else if(tr[p].key == key) tr[p].cnt ++;//已经存在key就直接将其++
else if(tr[p].key > key)//key < p.key 就向左儿子方向找
{
insert(tr[p].l, key);//先递归key找到位置放好之后,回溯的时候用p.val和p的左儿子p.l.val维护大根堆
if(tr[p].val < tr[tr[p].l].val) zig(p);
}
else
{
insert(tr[p].r, key);
if(tr[p].val < tr[tr[p].r].val) zag(p);
}
pushup(p);//回溯回来更新节点p的信息
}
void remove(int &p, int key)
{
if(!p) return ;//不存在该节点,该题不存在这种情况
else if(tr[p].key == key)//找到key
{
if(tr[p].cnt > 1) tr[p].cnt --;//个数大于1
else if(tr[p].l || tr[p].r)//个数为1,要删除就要先将其璇至叶子结点;存在左或右儿子
{//有两种情况:1.只存在某一个儿子,那么一定可以左旋或右旋 2.存在两个儿子,那么val是随机产生的,一定不是一样的,那么可以按照val将p与左儿子或右儿子进行左旋或右旋
//所以一定可以将p左旋或右旋达到让p下移的目的
//不存在左儿子或者右儿子的val > p.val那么就可以左旋
if(!tr[p].l || tr[tr[p].r].val > tr[p].val)//
{
zag(p);
remove(tr[p].l, key);
}
else
{
zig(p);
remove(tr[p].r, key);
}
}
else p = 0;//如果为叶子结点直接删掉
}
else if(tr[p].key > key) remove(tr[p].l, key);//p.key > key 就向左儿子方向找
else remove(tr[p].r, key);//向右儿子方向找
pushup(p);//更新父节点
}
int get_rank_by_key(int p, int key)//通过数值找排名
{
if(!p) return 0;//如果不存在就返回,本题不存在该情况
else if(tr[p].key == key) return tr[tr[p].l].size + 1;//如果p.key = key 那么排名为左子树数量+1
else if(tr[p].key > key) return get_rank_by_key(tr[p].l, key);//p.key > key向左儿子找
else return get_rank_by_key(tr[p].r, key) + tr[p].cnt + tr[tr[p].l].size;//向右儿子找,排名为左子树大小+p.key数量+在右子树的排名
}
int get_key_by_rank(int p, int rank)//通过排名找数值
{
if(!p) return 0;//如果不存在就返回,本题不存在该情况
else if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);//如果左子树大小 >= rank那么这个数一定在左子树中
else if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;//如果左子树+p.key的数量才 >= rank 那么这个数一定是p.key
else get_key_by_rank(tr[p].r, rank - tr[p].cnt - tr[tr[p].l].size);//否则就在右子树中
}
int get_prev(int p, int key)//找严格小于key的最大数
{
if(!p) return -INF;//不存在小于key的数那么就返回负无穷
else if(tr[p].key >= key) return get_prev(tr[p].l, key);//如果p.key >= key 那么严格小于key的数一定在左子树中
else return max(tr[p].key, get_prev(tr[p].r, key));
/*当tr[p].key < key:
当p无右子树那么小于key的最大数为p.key
当存在右子树那么小于key的最大数一定是右子树中的最小值,而这个最小值也是大于p.key
所以将两种情况结合起来就要取一个max
*/
}
int get_next(int p, int key)//找严格大于key的最小数
{
if(!p) return INF;
else if(tr[p].key <= key) return get_next(tr[p].r, key);
else return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
build();
int n, op, x;
scanf("%d", &n);
while(n--)
{
scanf("%d%d", &op, &x);
if(op == 1) insert(root, x);
else if(op == 2) remove(root, x);
else if(op == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
else if(op == 4) printf("%d\n", get_key_by_rank(root, x + 1));
else if(op == 5) printf("%d\n", get_prev(root, x));
else printf("%d\n", get_next(root, x));
}
return 0;
}