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

happybob · 2025-11-08 12:14:36 · 题解

令 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 弹出。即你需要维护一个序列，支持末尾加入删除，开头删除，查询全局最小值，利用双栈模拟队列的结构即可做到线性。