NOIP2024 T4

Rainbow_qwq · 2024-12-17 15:38:03 · 题解

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

特判掉 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_i = \min(a_i,a_{i+1}) 的操作，操作完长度减一
• 求 a 数组区间最大值

假设 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)。

Code