NOIP2024 T4

一个硬维护的做法，居然没人是这样做的（

特判掉 $k=1$ 的询问，对于 $k\ge 2$，区间 LCA 的深度为 $\min_{l\le i < r} \operatorname{dep}_{\operatorname{LCA}(i,i+1)}$。（证明考虑一下虚树，这里不再赘述）

那么问题可以转化为：有一个序列 $a$，询问 $l,r,k$，求 $\max_{p\in [l,r]} (\min_{i\in [p,p+k-1]} a_i)$。

这可以看作：把 $a$ 数组进行 $k-1$ 次 $a_i = \min(a_i,a_{i+1})$ 的操作，然后求 $a$ 的区间最大值。

把询问按照 $k$ 排序，问题转化为：

假设 $a$ 的所有元素不同，否则给 $a$ 的相同元素也钦定大小顺序。

考虑直接维护 $a$ 中的每个值域连续段。每次进行 $a_i = \min(a_i,a_{i+1})$ 的操作后，每个连续段长度可能变化 $-1/0/1$。

如果连续段的值比两边都小，长度会加 $1$；比两边都大，长度会减 $1$；否则长度不变。

具体的：设 $l,r$ 为 $i$ 这个段左边和右边的连续段。考虑设 $d_i = [a_i < a_l] + [a_i < a_r] - 1$，在每一次变化后，$a_i$ 这个值的连续段长度加上 $d_i$。（如果 $a_l/a_r$ 不存在则设 $a_l/a_r=-\infty$）

如果一个连续段长度变为 $0$，则这个连续段要删掉，并且更新左边、右边连续段的 $d_i$。

可以在线段树上维护每个连续段的 $a_i,d_i$ 和长度，以及当前 $d_i=-1$ 的连续段的长度最小值，用链表维护删除。

查询在线段树上二分一下，修改需要打标记，然后不断删除长度变为 $0$ 的连续段。

时间复杂度 $O((n+q)\log n)$。