题目来源：改编自 洛谷 P3369【模板】普通平衡树。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。
学习目标
前置知识与环境
先阅读第 8.3 节 平衡查找树的"AVL 树"（含"四种失衡形态""LR 与 RL：先把折线拉直"）、"AVL 插入流程""AVL 删除"与"AVL 的高度与复杂度"几节。
与 Lab 08-E-01（普通 BST 增删查）的差异：E-08-01 的数据是随机到达、规模很小，普通 BST 就够用；本题操作数达到 10⁵，且压力用例里包含升序插入序列——普通 BST 会退化成一条长度 5×10⁴ 的链，每次操作
在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。
任务
维护一个可重复的整数多重集合，初始为空，依次处理 n 个操作：
| 操作 | 含义 |
|---|---|
1 x | 插入 x（可与已有元素重复） |
2 x | 删除一个 x（若有多个只删一个；数据保证 x 存在） |
3 x | 查询 x 的排名：严格小于 x 的元素个数 + 1（x 不一定在集合中） |
4 r | 查询排名为 r 的数（即第 r 小；保证 1 ≤ r ≤ 当前元素个数） |
5 x | 查询 x 的前驱：严格小于 x 的最大元素（数据保证存在） |
6 x | 查询 x 的后继：严格大于 x 的最小元素（数据保证存在） |
输入格式
- 第一行：一个整数
n，为操作总数； - 接下来
n行：每行两个整数opt x，含义见上表。
输出格式
对每个 opt = 3/4/5/6 的操作，输出一行一个整数；opt = 1/2 不产生输出。
数据范围与限制
| 项目 | 范围 |
|---|---|
操作数 n | 1 ≤ n ≤ 10⁵ |
元素值 x | |x| ≤ 10⁷ |
排名查询 r | 保证 1 ≤ r ≤ 当前元素个数 |
| 前驱 / 后继 | 数据保证存在（不必处理"不存在"的输出） |
| 删除操作 | 保证被删元素在集合中 |
| 实现要求 | 手写 AVL 树（不得用 std::map / std::multiset 等关联容器代替），插入、删除都要维护 size |
| 时间复杂度要求 | 每个操作 |
正常、边界与错误情况
- 重复值：插入同一个值多次后，
3的排名要把所有严格小于它的元素都数进去；删除只移除一个实例； - 排名边界：查询最小元素的排名（结果为 1）与最大元素的排名（结果为当前元素个数）；第 1 小与最后一小；
- 前驱后继：前驱可能就是相邻的重复实例之间的关系（如多重集合中 0 有多个时，0 的后继是下一个更大的值而非 0 本身）；
- 空集合：操作 4/5/6 保证合法，因此不会在空集合上查询，但删除使集合反复变空又变非空的过程要正确维护
size。
样例
样例 1
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598106465
84185
4927374 1 时集合里只有 106465，第 1 小就是它；6 81968 时集合为 {84185, 89851, 106465, 317721, 460929, 644985}，大于 81968 的最小元素是 84185；插入 492737 后，5 493598 的前驱是 492737。
样例 2
12
1 5
1 3
1 5
1 8
3 5
4 2
2 5
3 5
5 5
6 5
4 1
4 32
5
2
3
8
3
8逐条解释：插入后多重集合为 {3, 5, 5, 8}；3 5 的排名 = 严格小于 5 的元素个数 1，再加 1 得 2；4 2 是第 2 小 = 5；2 5 只删掉一个 5，剩 {3, 5, 8}；3 5 仍为 2；5 5 的前驱是 3，6 5 的后继是 8；4 1 是 3，4 3 是 8。
实现提示
- 结点里同时维护
height和size，旋转后先更新被转下去的结点，再更新新根；漏掉size会让排名与第 k 小悄悄出错，而高度看起来一切正常； - 插入递归返回新的子树根，回溯时逐层
rebalance；删除"至多一个孩子"的情形直接让孩子顶替，把再平衡交给回溯路径； - LR 形态的判据是"左孩子的左子树高度 小于 左孩子的右子树高度"；删除时可能遇到左右等高、单旋即可恢复的情况，判据写成
<=与<都要推一遍为什么正确； rankOf(x)沿树下行：x不大于当前键就往左走，否则把"左子树 size + 1"累加进答案再往右走；kth(k)反向利用同一个size；- 对拍是本章核心题的必做步骤：写一个基于有序数组（或
multiset语义）的暴力程序，随机生成小规模混合操作，与你的 AVL 逐行比对输出。重复值 + 删除的组合最容易暴露size维护的 bug。
运行
make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-08/exercise/E-08-09-balanced-tree-template需要单用例或严格评分时使用 make run CASE=006-stress-sorted 与 make score；也可用 pnpm lab:score -- labs/chapter-08/exercise/E-08-09-balanced-tree-template 兜底。
完成清单
思考与复盘
- 对拍过程中你抓到过什么 bug？是旋转后忘记
pull、判据写反，还是删除后继时忘了维护size？写出定位过程。 - 同样是平衡树，AVL 在"查询多、修改少"和"修改频繁"两种负载下与红黑树（8.3 节）相比各有什么优劣？
- 若把操作 3 改成"查询 x 的排名，x 可能不存在但仍返回公式值"，你的实现需要改动吗？若要求支持"删除所有等于 x 的元素"，删除的复杂度会怎样变化？