题解：P11364 [NOIP2024] 树上查询

Larunatrecy · 2024-11-30 21:33:04 · 题解

首先不难证明 \operatorname{LCA}(l,r)=\min\limits_{i=l}^{r-1}{dep_{\operatorname{LCA}(i,i+1)}}，考虑相邻两个点的 LCA 深度构成的序列，我们就是要查询这个序列上某个区间内所有长度至少为 k-1 的区间的最小值的最大值。

建出笛卡尔树后，我们可以求出以每个数作为最小值的极长区间 [l_i,r_i]，那么如果把 (l,r) 看成二维平面上的点，极长区间 [l_i,r_i] 的子区间就是 (l_i,r_i) 的右下矩形。

而查询的则是 (l,l+k-1) \to (r-k+1,r) 这一条斜率为 1 的线段。

那么容易转化为：

• 有 O(n) 个点，每个点会对其右下矩形取 \max；有 m 个询问，每个询问给一个斜率为 1 的线段，查询线段上的最大值。

如图，蓝色为查询线段，我们将其左上区域拆分成红色，绿色，黄色区域的并集，这三个区域都是一个前缀矩形，直接做三次扫描线维护区间最大值即可。

黄色区域只需要将平面旋转 45 度就变成普通扫描线了。

复杂度 O(n\log n)。