[NOIP2025] 序列询问

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

$1.$ $l,r$ 在同一个块 $d$ 中：对于每一个块，内部的区间的长度一定不会超过 $R$，所以仅需要考虑 $\geq L$ 一侧的贡献，可以想到每次分块使得限制减少一，故可以再对这个块 $d$ 按照 $L$ 为大小进行分块，我们把再分块的块称为小块，则有这样的几种情况：

$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)$。