时间限制： 1.5 秒

空间限制： 64 MB

题目背景

给定以下二叉搜索树的节点接口定义：

struct BstNode
{
    int key;           // 关键码
    BstNode *fa;       // 父亲（对于根节点为 NULL）
    BstNode *lc, *rc;  // 左儿子和右儿子
    int size;          // 以当前节点为根的子树节点个数
};

题目描述

你需要实现 count 函数，传入二叉搜索树的根节点 $T$，以及值域的区间端点 $lo,hi$ （区间范围是左闭右开的），你需要找出二叉搜索树中，节点的关键码范围介于 $[lo,hi)$ 的节点个数。

无论做出统计的总数有多大，单次查询的时间复杂度不得超过 $O(h)$（其中 $h$ 为二叉搜索树的高度）、额外辅助空间的复杂度为 $O(1)$。

为了简化本题实现，我们保证本题二叉搜索树上的所有的关键码互异。

交互方式

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

你提交的代码需要包含头文件 count.h。

你需要实现一个函数 int count(BstNode*, int, int)，传入参数为二叉搜索树的根节点 $T$，以及值域的区间端点 $lo,hi$ （区间范围是左闭右开的）。你需要在时间复杂度 $O(h)$ 和空间复杂度 $O(1)$ 的限制下，找出二叉搜索树中，节点的关键码范围介于 $[lo,hi)$ 的节点个数。

以下我们给出一个代码提交实例（固定返回 0，仅作为可以通过编译的示例，不保证能得分）：

#include "count.h"
int count(BstNode* T, int lo, int hi)
{
    return 0;
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 count.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 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒交互库先读入一个整数 $q$ 表示对二叉搜索树进行插入或者查询的总数。接下来读入 $q$ 行，表示不同操作：

• $1~x$：表示在二叉搜索树中插入 $x$。
• $2~lo~hi$：表示从二叉搜索树的根节点开始查询树中节点的关键码范围介于 $[lo,hi)$ 的节点个数。

对于所有的操作 2，都会输出一行一个非负整数，表示查询的节点数目。

5
1 10
1 20
2 10 20
1 30
2 10 31

1
3

样例 1 解释

总共 5 次操作，先在二叉搜索树中插入了 $10,20$，查询在 $[10,20)$ 的关键码，总计 1 个节点。然后再插入 $30$，查询在 $[10,31)$ 的关键码，总计 3 个节点。

子任务

对于所有数据，保证操作次数 $q\le 10^6$，查询时一定有 $lo\le hi$，所有操作数的绝对值不超过 $10^9$，在二叉搜索树上的所有关键码互异，任何时候的二叉搜索树高度不超过 $100$。

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

提示

如果你手写过在算法竞赛当中可以实装使用的平衡树，那么实现本题可能会轻松很多。

来源

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