题解：P11405 [RMI 2020] 秘鲁 / Peru

令 $f_i$ 表示前 $i$ 个的答案，$\mathrm{submax}(i,j) = \max \limits_{x=i}^j s_x$。则 $f_i = \min \limits_{j \geq i - k + 1} \{ f_{j-1} + \mathrm{submax}(j,i)\}$。

直接利用线段树和单调栈不难做到 $O(n \log n)$，估计是过不了的。

考虑决策点 $j$，必定有 $j=i-k+1$ 或 $s_{j-1}$ 为 $[j-1,i]$ 的严格后缀最大值，否则令决策点为 $j-1$ 显然不劣。

维护后缀最大值的位置然后维护一个能支持插入删除查询最小值的 multiset 也可以做到 $O(n \log n)$，利用懒惰删除优先队列就可以得到一个常数非常小的做法，据说可以通过。

进一步，分析 $i \gets i+1$ 的本质，是把后缀最大值这个序列末尾删除一些数，然后末尾加入，以及将 $j<i-k+1$ 的 $j$ 弹出。即你需要维护一个序列，支持末尾加入删除，开头删除，查询全局最小值，利用双栈模拟队列的结构即可做到线性。