[NOIP2025] 序列询问

· · 题解

这个问题看上去比较双栈模拟，所以一个非常自然的想法是考虑分块。首先将原序列按照 R 的大小分块，则 l,r 只有可能是属于同一块或处在相邻两个块的，分别考虑两种情况：

* $p$ 与 $l$ 或 $r$ 处在同一个小块，不妨考虑 $p$ 与 $l$ 处在同一个块的情况，对于 $l\leq p$，此时对于任意的 $r$，若 $r-l+1\geq L$，则 $p$ 一定在 $[l,r]$ 之中，故只需考虑对于每一个 $l$ 求出最优的 $r$，这在块 $d$ 中对应一段后缀，然后在小块中做个前缀 $\text{max}$ 即可。 * $p$ 不与 $l,r$ 中的任意一个处在同一个小块，此时相当于没有对于区间长度的限制，对于每一个小块，计算前面的小块中 $-s_{ps-1}$ 的 $\text{max}$ 与后面的小块中 $s_{ps}$ 的 $\text{max}$ 即可求出跨过该小块的贡献。 $2.$ $l,r$ 处在相邻的块中，$l$ 在块 $d$ 中，$r$ 在块 $d+1$ 中，不妨统计的结果的 $p$ 在块 $d$ 中，在块 $d+1$ 是对称的。对于 $l\leq p$，任意在块 $d+1$ 的 $r$ 均满足 $p\in [l,r]$，故对于每一个 $l$，求出最优的 $r$，求解 $r$ 可以单调队列简单维护。然后对块 $d$ 作个前缀 $\text{max}$ 则可以求出跨过 $p$ 的结果。 两部分对于每组询问 $O(n)$，故总复杂度 $O(nq)$。