P2586 意欲现

这题咋这么难qwq，以下是我个人理解，若有问题欢迎指出

一.dp

这题第一眼就有一个看起来很不优的dp，令 $f_{i,j}$ 为 $[1,i]$ 操作变为单调不降且第 $i$ 个数为 $j$ 的最少操作次数。

转移剥蒜就是 $f_{i,j} = \mathop{min}\limits_{k \le j}(f_{i-1,k}+|a_i-j|) $ 。 这样复杂度是 $O(an)$ 的，其中 $a$ 是值域，这个显然是过不了的。

一.注意到神秘小结论然后贪心

首先有一个神秘小结论，就是对于 $a \le c \le b$ ，将 $a,b$ 同时变为 $c$ 的操作次数与 $c$ 是无关的，证明即 $opts = c - a + b - c = b - a$ 。

然后再说如何贪心，首先前面的数越小对后面越有利，那么根据这个贪心结论我们就可以让前面的数尽可能小，那么我们就需要维护一个前缀最大值，可以直接开个大根堆来维护，具体的，如果我们新加入一个数 $x$ ，$x$ 要小于前缀最大值，那么我们设其最大值为 $op$ ，然后就将 $op - x$ 计入贡献，那么我们就可以将这个最大值剔除，然后替换成两个 $x$ ，如果小于那直接将 $x$ 入堆。

简单说明一下正确性：

一，为什么要改为 $x$ 而不是可以更小，首先对于堆贪，是不是可以更小这种决策是可以放在后面决策的，我们目前只需要确保局部最优。

二，如何满足题目要求一定是原数列里的数，如果说将 $op$ 改为 $x$ 后仍然是最大值，其实就天然满足是原数列里的数，若改完之后不是最大值，即存在一个原数列里的数 $x \le a_k \le op$ ，根据最开始的结论，这个具体改后的值我们是不需要管的，也就是说在保证结果不变的情况下，一定有一种解满足题意