昨天小码匠刚学了平衡树，晚上快9点的时候把平衡树的板子敲完。
累坏宝宝了，然后又整理了下笔记，就下了。
今天晚上自习时，补了2道白天没做完的题，又给他安排了2道平衡树
- 一道数据加强版：还算顺利；
- 另外一道，快到下课没调试出来，只能后面再抽时间补题了；
划重点：孩子们假期学习，还是要规划好后面的补题，别学了很多新知识，狗熊掰棒子，后面都忘了。
好了，比较晚了，下面分享下小码匠打的板子代码。
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
typedef long long ll;
#define ls t[id].son[0]
#define rs t[id].son[1]
const int maxn = 1e6 5;
struct point {
int val, dat, size, cnt;
int son[2];
// 分别表示值，优先级，子树大小，包含的副本数，左右子节点
} t[maxn];
int k = 0, root;
int add(int v) {
t[ k].val = v;
t[k].dat = rand();
t[k].size = 1;
t[k].cnt = 1;
return k;
}
void push_up(int id) {
t[id].size = t[ls].size t[rs].size t[id].cnt;
// 本节点子树大小 = 左儿子子树大小 右儿子子树大小 本节点副本数
}
void rotate(int &id, int d) { // id是引用传递，d为旋转方向，0为左旋，1为右旋
int u = t[id].son[d ^ 1];
t[id].son[d ^ 1] = t[u].son[d];
t[u].son[d] = id;
id = u;
push_up(t[id].son[d]);
push_up(id);
// 旋转以后size会改变，看图就会发现只更新自己和转上来的点，push_up一下,注意先子节点再父节点
// 旋转实质是在满足BST的性质的基础上比较优先级，通过交换本节点和其某个叶子节点把链叉开成二叉形状，从而控制深度，可以看图理解一下
}
void put_into(int &id, int v) {
if (!id) {
id = add(v); // 如果以前没有这个节点就新建一个
return;
}
if (v == t[id].val) {
t[id].cnt;
} else {
int d = v < t[id].val ? 0 : 1; // d代表方向，按照BST的性质，小于本节点则向左，大于向右
put_into(t[id].son[d], v);
if (t[id].dat < t[t[id].son[d]].dat) {
rotate(id, d ^ 1); // 与左节点交换右旋，与右节点交换左旋
}
}
push_up(id); //现在更新一下本节点的信息
}
void detach(int &id, int v) {
if (!id) {
return; // 如果发现查不到这个节点，即该点不存在，直接返回
}
if (v == t[id].val) { // 如果检索到了这个值
if (t[id].cnt > 1) {
--t[id].cnt;
push_up(id);
return;
} //若副本不止一个，减去一个就好
if (ls || rs) { // 发现只有一个值，且有儿子节点,我们只能把值旋转到底部删除
if (!rs || t[ls].dat > t[rs].dat) {
// 当前点被移走之后，按照优先级，选择左右儿子中更大的补上来
rotate(id, 1);
detach(rs, v);
// 右旋是与左儿子交换，当前点变成右节点；左旋则是与右儿子交换，当前点变为左节点
} else {
rotate(id, 0);
detach(ls, v);
}
push_up(id);
} else {
id = 0; // 发现本节点是叶子节点，直接删除
}
return; // 这个return对应的是检索到值的所有情况
}
if (v < t[id].val) { //继续BST性质
detach(ls, v);
} else {
detach(rs, v);
}
push_up(id);
}
int get_rank(int id, int v) {
if (!id) {
return 1; // 若查询值不存在，返回；因为最后要减一排除哨兵节点，想要结果为-1这里就返回0
}
if (v == t[id].val) {
return t[ls].size 1;
// 查询到该值，由BST性质可知，该点左边值都比该点的值(查询值)小，故rank为左儿子大小 1
} else if (v < t[id].val) {
return get_rank(ls, v);
// 发现需查询的点在该点左边，往左边递归查询
} else {
return t[ls].size t[id].cnt get_rank(rs, v);
// 若查询值大于该点值。说明询问点在当前点的右侧，且此点的值都小于查询值，所以要加上cnt[id]
}
}
int get_val(int id, int rank) {
if (!id) {
return 1e9; // 一直向右找找不到，说明是正无穷
}
if (rank <= t[ls].size) {
return get_val(ls, rank); // 左边排名已经大于rank了，说明rank对应的值在左儿子那里
} else if (rank <= t[ls].size t[id].cnt) {
return t[id].val; // 上一步排除了在左区间的情况，若是rank在左与当前节点中，则直接返回当前节点中区间的值
} else {
return get_val(rs, rank - t[ls].size - t[id].cnt);
// 剩下只能在右区间找了，rank减去左区间大小和中区间，继续递归
}
}
int get_pre(int v, int id) {
int pre = 0; // 递归不好返回，以循环求解
while (id) { // 查到节点不存在为止
if (t[id].val < v) {
pre = t[id].val;
id = rs; // 满足当前节点比目标小，往当前节点的右侧寻找最优值
} else {
id = ls; // 无论是比目标节点大还是等于目标节点，都不满足前驱条件，应往更小处靠近
}
}
return pre;
}
int get_next(int v, int id) {
int next = 0;
while (id) {
if (t[id].val > v) {
next = t[id].val;
id = ls;
} else {
id = rs;
}
}
return next;
}
void solve() {
int n;
root = add(-1e9);
t[root].son[1] = add(1e9);
push_up(root);
cin >> n;
for (int i = 1; i <= n; i ) {
int opt, x;
cin >> opt >> x;
if (opt == 1) {
put_into(root, x);
} else if (opt == 2) {
detach(root, x);
} else if (opt == 3) {
cout << get_rank(root, x) - 1 << 'n';
} else if (opt == 4) {
cout << get_val(root, x 1) << 'n';
} else if (opt == 5) {
cout << get_pre(x, root) << 'n';
} else if (opt == 6) {
cout << get_next(x, root) << 'n';
}
}
}
void best() {
}
int main() {
solve();
// best();
return 0;
}
