题解

Iniaugoty · 2026-03-01 11:24:00 · 题解

没有 + 1 操作的答案是逆序对个数，所以我们的操作一定是先 + 1 得到一个新序列 b，问题转化成最小化 \sum_{i=1}^n \left( b_i - a_i + \sum_{j=1}^{i-1} [b_j > b_i] \right)，其中 - a_i 是固定的。

考虑一个从前往后贪心的过程，当前已经确定了 b_1, \cdots, b_{i-1}，需要考虑 b_i 的取值。记 c_v = v + \sum_{j=1}^{i-1} [b_j > v]，我们声称：取 c_v 最小的 v 是最优的。

这个过程相当于是：从 1 扫描到 n，维护一个值域上的序列 c，初始 c_v = v；每次先取 [a_i, \infty) 的最小值 c_p，将 b_i 设为 p，令答案增加 c_p，然后将 [1, p - 1] 进行 + 1。

至于她为什么是对的，我们考虑如果选择了一个 c_q > c_p 的 q 那他为什么更劣，讨论一下：

• 若 q > p 则是显然的，因为在 c_q > c_p 已经不优的前提下，还会额外使 [p, q) 后面的贡献 + 1。

• 若 q < p，q 相比 p 唯一好的地方是 [q, p) 的贡献不会被 + 1 了，但这其实是没用的，因为这样下来一定会使后面 c_{[q, p)} > c_p，而在一个后缀中选数，如果能选到 [q, p) 肯定还会选 p。为了证明的严谨这里似乎需要归纳一下。

我们可以直接用线段树维护这个过程，时间复杂度是 O(n \log n)。至于一些细节，你会发现每个数修改成一个在原序列出现过的数一定是不劣的，所以可以直接离散化；如果出现多个最小的 c_v，选择 v 最小的一个肯定也是不劣的。

建议题解附有代码，也可以在题目分析后完整给出。