P11239 [KTSC 2024 R2] 跳跃游戏 - Solution

已计算完毕的 $f$ 单调不降，这是显然的，所以我们只用考虑上一层的 $f$。我们默认在线段树里面先将所有的 $a_i$ 加好，这是若干个区间加，均摊 $\Theta(q)$ 个。

我们的 $f$ 要么来自上一层 $+a_i$，要么来自本序列的前面的某个 $f$。考虑这种差异的原因，当然是因为 $a_i < a_{i - 1}$（或者 $f_{i - 1}$ 继承过来的更大），导致 $i$ 往后的一段 $a$ 跟 $a_i$ 相同的元素 $f$ 取 $f_{i - 1}$ 更优秀。由于 $f$ 具有单调性，这必然是 $i$ 开头的一段区间，可以线段树上二分求出，然后做区间覆盖。

不难发现，对于 $a_{i}$ 相同的相邻的 $f$，不可能后面的取 $\max$ 前面却不取，所以只考虑 $a_i$ 等价段开头的 $f$ 即可。

还有一个问题，我们现在的复杂度是 $\Theta(\frac{n}{k} + q \log q)$，$k$ 很小怎么办。