时间限制： 1.0 秒

空间限制： 512 MB

题目背景

AVL 树是一种自平衡的二叉搜索树。在 AVL 树中，任何节点的两个子树高度相差不超过 1。

我们知道，AVL 树在删除一个节点后如果失衡，可以通过适当的调整来恢复平衡。

如果我们发现节点 $g$ 失衡，则调整相邻三层中确定的三个节点，按照高度依次递减次序命名为 $g,p,v$（其中 $g$ 是 $p$ 的父节点，$p$ 是 $v$ 的父节点）。

给定 AVL 树节点的接口定义：

struct AVLNode
{
    int val; // 关键码
    AVLNode *fa;
    AVLNode *lc, *rc;
    int height; // 子树高度
};

在本题中，我们定义只有一个节点的树，其树高为 1。

一般的 AVL 旋转调整可以归为 zag 和 zig 两种基本的等价旋转变换，并通过单旋和双旋完成。

但是根据失衡节点与儿子和孙子节点的位置关系，可以引入一种简明的统一处理方法，将局部的 3 个节点与 4 棵子树，按照 {T0, a, T1, b, T2, c, T3}。 的中序遍历进行重新排列，即可对应到上述的旋转变换。

其中 connnect34 的接口如下，按照顺序传入 3 个节点与 4 棵子树的根节点，即可在重排列后返回由他们组成的子树的根，也就是 b。

AVLNode *connect34(AVLNode *a, AVLNode *b, AVLNode *c,
                   AVLNode *T0, AVLNode *T1, AVLNode *T2, AVLNode *T3);

题目描述

在本题中，你需要根据给定的失衡 $g$ 找出对应的 $p$ 和 $v$，并通过调用 connect34 函数对 AVL 树进行重平衡调整。

你需要实现以下两个函数：

AVLNode *target_child(AVLNode *);

本题的交互库会先传入 $g$ 来确定对应的 $p$，再传入 $p$ 来确定对应的 $v$，你实现的 target_child 需要正确返回重平衡需要使用的目标子节点。

AVLNode *tuning(AVLNode *g, AVLNode *p, AVLNode *v);

根据确定的 $g,p,v$ 的不同情况调用 connect34 函数，并返回原本以 $g$ 为根的子树经过调整后的树根。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 avl.h，需要实现的函数见【题目描述】。

你可以调用以下函数：

bool islc(BinNode *u);
bool isrc(BinNode *u);

分别用于判断传入的二叉树节点是否为其父节点的左子节点/右子节点。当传入节点为空或不存在父亲时，直接返回 false。

AVLNode *connect34(AVLNode *a, AVLNode *b, AVLNode *c,
                   AVLNode *T0, AVLNode *T1, AVLNode *T2, AVLNode *T3);

见题目背景，可以根据中序遍历形式对 3 个节点与 4 棵子树进行嫁接，调整为以 b 为根的子树。

需要注意的是，由于本题的判题方式需要，交互库中对于 AVLNode 节点接口定义会额外增加其他成员或函数，黑盒交互库的额外成员与白盒交互库定义略有不同，因此不能保证访问。但是你可以正常访问【题目背景】中的成员。

以下我们给出一个代码提交实例（不做任何操作只返回传入的节点，仅作为可以通过编译的实例，不保证能得分）。

#include "avl.h"
AVLNode *target_child(AVLNode * u) { return u; }
AVLNode *tuning(AVLNode *g, AVLNode *p, AVLNode *v) { return g; }

白盒交互库实例

具体见附加文件区的 interactor.cc 和 avl.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒库在动态维护一个可重集合 $M$，并且提供以下操作：

1. 向 $M$ 中插入一个数 $x$。
2. 从 $M$ 中删除一个数 $x$，如果有多个 $x$ 同时在 $M$ 中，只删除其中一个。
3. 查询 $M$ 中有多少个数严格小于 $x$，将得到的答案 +1 再输出。
4. 查询将 $M$ 从小到大排列后，排为第 $x$ 位的数，排位从 1 开始计算。
5. 查询 $M$ 中严格小于 $x$ 的最大数。
6. 查询 $M$ 中严格大于 $x$ 的最小数。

保证：

• 对于操作 2，删除时 $M$ 中至少存在一个 $x$。
• 对于操作 3,5,6，不保证当前 $M$ 中存在数 $x$。
• 对于操作 5,6，保证答案一定存在。

即：实现普通平衡树的功能。

交互库对于每个操作 3,4,5,6，输出一行一个整数，表示对应查询的答案。黑盒交互库虽然不同于白盒交互库，但是在完全相同的输入输出下格式实现完全相同的功能测试。

请尤其留意交互库中 rebalance 函数对上述两个函数的调用过程。

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

106465
84185
492737

子任务

对于所有数据，保证 $1\le n\le 10^5,-10^7\le x\le 10^7$。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

在实现 tuning 的过程中，先想好有多少种情况，再手动推演进行单旋/双旋的过程，从而确定如何调用 connnect34。

来源

清华 826 考研初试 2021 - 算法大题（1）