信竞学习笔记：[NOIP2024] 树上查询

Tiger

发表于 2026-07-25

更新于 2026-07-25

学习笔记

4 2.6~3.4 分钟 1186

注：这是本人的课堂笔记。

题目：P11364

题意概述

有一棵有根树，根节点编号为 $1$ 。定义深度 $\text{dep}_ u$ 定义为 $u$ 到 $1$ 的简单路径上的结点数量。根节点深度为 $1$ ，定义 $\text{LCA*}(l, r)$ 为编号在 $[l, r]$ 中所有结点的最近公共祖先，即 $l, l + 1, \dots , r$ 的公共祖先结点中深度最大的结点。

有 $q$ 个询问。每个询问给出三个参数 $l, r, k$ ，代表给出 $[l, r]$ 中任意长度大于等于 $k$ 的连续子区间的最近公共祖先深度的最大值，即

\max_{l\le l'\le r'\le r \land r'-l'+1\ge k}\text{dep}_ {\text{LCA*}(l', r')}

处理这些询问。

分析

将节点编号从小到大排，求出两两相邻的节点的 LCA 深度。有如下结论：

\text{dep}_{\text{LCA*}(l, r)} = \min\limits_{i=l}^{r-1} \text{dep}_{\text{LCA}(i, i+1)}

解释：对于任意 $l \leq i < r$ ， $\text{dep}_{\text{LCA*}(l, r)} \leq \text{dep}_{\text{LCA}(i, i+1)}$ 。同时，必然能找到两个点，使得二者位于区间 LCA 的不同分支，所以 $\text{dep}_{\text{LCA*}(l, r)} \geq \min\limits_{i=l}^{r-1} \text{dep}_{\text{LCA}(i, i+1)}$ ，所以有如上结论。

对于求得的每个 LCA 深度尽可能拓展所属区间，使得其 LCA 深度保持不变。则对于拓展所得区间，从中任选一段区间，其 LCA 深度最坏（最小）为上述 LCA 深度。我们称这些区间为贡献区间，用形如 $(x, y, v)$ 的三元组的表示，代表在区间 $[x, y]$ 中任选区间，其区间 LCA 深度最坏为 $v$ 。例如对于本题样例 1，有三个贡献区间，分别为 $(1, 6, 1)$ 、 $(2, 6, 2)$ 、 $(2, 4, 3)$ （重复的剔除，实际代码中可以不去重）。

根据上面的结论，小的深度的贡献可以把大的深度的贡献覆盖掉，但大得深度的贡献不能将小的深度的贡献覆盖掉。问题转化为求每一个数字左边或右边第一个出现的比它本身小的数。这就是其能拓展的范围。这个问题可以用单调栈解决。

有了贡献区间后，再看询问区间。询问区间同样也是一个三元组，我们用 $(l, r, k)$ 进行表示，含义如题目所示。要找 $\text{len}([x, y] \cap [l, r]) \geq k$ ，则其中 $v$ 最大的区间 $[x, y]$ 的 $v$ ，即为本询问的答案。对于每个询问，暴力比较的时间复杂度约为 $O(n^2)$ 。

考虑 $[x, y] \cap [l, r]$ ，有如下几种情况： $[x, y] \subseteq [l, r]$ 、 $[l, r] \subseteq [x, y]$ 、 $[l, r]$ 与 $[x, y]$ 互不包含但相交。最后一种情况还可以分为相交区间为 $[x, r]$ 和 $[l, y]$ 的情况。为简便，记四种情况依次分别为 A、B、C、D。

对于情况 A 和 C，二者都有 $y \geq r \land x \leq r - k + 1$ ，记作情况 1；对于情况 B 和 D，二者都有 $y \leq r \land y - l + 1 \geq k \land y - x + 1 \geq k$ 。三维偏序不好处理，可以转化为 $l + k - 1 \leq y \leq r \land y - x + 1 \geq k$ ，这样就可以转化为二维偏序，记作情况 2。

考虑扫描线。对于情况 1，当扫到 $r$ 时，要找到所有贡献区间中 $y_i \geq r$ ，且进一步满足 $x_i \leq r - k + 1$ 的所有 $(x_i, y_i, v_i)$ 中最大的 $v_i$ 。

考虑从后往前扫描，将询问区间和贡献区间分别按照 $r$ 和 $y$ 挂在相应的节点下面，每次把贡献区间放入一个线段树中（如何实现稍后再说），此时放入线段树中的贡献区间恰巧就是满足 $y \geq r$ 的所有贡献区间。注意要先加贡献，再处理询问，因为 $y \geq r$ 能取到等号。

处理情况 1 的第二个不等式。由于 $x \leq r - k + 1$ 是一个前缀，又要求最大的 $v$ 值，所以可以以 $x$ 为下标， $v$ 为值建立最大值线段树。每次查询 $[1, r-k+1]$ 区间内的最大值即可。

接下来考虑情况 2。和情况 1 类似，对于第二个不等式，使用扫描线逆序扫描；对于第一个不等式，使用线段树维护以 $y$ 为下标、值为 $v$ 的最大值不等式即可求解。最后再将两种情况的结果取最大值即可。

另外，对于 $k=1$ 的情况，实际上是查询 $[l, r]$ 区间中所有节点中最深节点得深度，可以直接用 ST 表维护查询。