知不可乎骤得，托遗响于悲风。

lzyqwq · 2024-12-01 16:44:21 · 题解

感谢这题给我送退役了。

题意很简洁了，这里不再概括。

考虑到 \text{dfn} 最小值和最大值两个点求一下 \text{LCA} 的做法和我一样没有前途，因此换一条路冲，注意到一个结论：

记 a_i=\text{dep}_{\text{LCA}(i,i+1)}，则当 l\ne r 时 \text{dep}_{\text{LCA}^*(l,r)}=\min\limits_{i=l}^{r-1}a_i。

证明：

• 随着区间的扩展 \text{LCA} 深度一定不升，因此 \text{LHS} \le \text{RHS}。
• 考虑区间 \text{LCA}=x，则一定存在区间内两个点 i,j(i<j) 来自于 x 的不同子树。此时 [i,j) 中一定存在一个位置 p 满足 p 和 p+1 来自不同子树，则 a_p 会取到 \text{dep}_x。

因此把 k=1 的询问判掉之后，令 r\leftarrow r-1,k \leftarrow k-1。则问题变成求一个子区间 [l',r']\sube [l,r] 满足 r'-l'+1\ge k 且区间最小值最大。