P12861 [NERC 2020 Online] Lookup Performance

**二叉搜索树**（binary search tree）是一种带根的二叉树，其节点存储的键值满足：每个节点的键值大于其左子树中所有节点的键值，并小于其右子树中所有节点的键值。 二叉搜索树可用于维护有序集合，并支持对集合执行多种查询操作。本题中我们考虑的查询是：在集合中查找位于区间 $[L, R]$ 内的值的数量。 设 $S$ 为二叉搜索树中所有键值的集合。给定两个值 $L$ 和 $R$，查询的目标是找出满足 $L \le x \le R$ 的 $x \in S$ 的数量。以下递归函数在调用 `lookup(root, L, R)` 时会计算该值，其中 `root` 是二叉搜索树的根节点。 ``` function lookup(v, L, R): if v == null: return 0 if L

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）——二叉搜索树的节点数量。 接下来的 $n$ 行描述树的节点。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $k_i$，分别表示第 $i$ 个节点的左子节点、右子节点和键值。如果节点没有左子节点或右子节点，则对应值为 $0$（$l_i = 0$ 或 $i < l_i \le n$；$r_i = 0$ 或 $i < r_i \le n$；$-10^9 \le k_i \le 10^9$）。树的根节点为节点 $1$，保证这是一棵合法的二叉搜索树。 注意，`v.min`、`v.max` 和 `v.count` 并未在输入中显式给出，因为它们可以通过 $l_i$、$r_i$ 和 $k_i$ 推导得出。 接下来一行包含一个整数 $q$（$1 \le q \le 200\,000$）——查询的数量。 接下来的 $q$ 行每行包含两个整数 $L$ 和 $R$（$-10^9 \le L \le R \le 10^9$）——作为 `lookup` 函数的参数。

输出 $q$ 行，第 $i$ 行包含一个整数——第 $i$ 个查询中 `lookup` 函数被调用的总次数。

翻译由 DeepSeek V3 完成