本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-13 20:08:15

模拟赛做到了这道题，感觉妙，写个题解。

首先发现原题等价于可以给某些数加上 $n$ 后再排成升序，这样在原序列上把加过的数排好序放到最后，剩余数排好序放到前面，只有分界点可能 $P_i>P_{i+1}$，符合原题意。

直接排序需要的交换次数为序列的逆序对数，我们在此基础上考虑给数加 $n$ 导致的变化量。首先有一个性质：若 $x<y$ 且 $P_x>P_y$，则给 $P_x$ 加却不给 $P_y$ 加一定不优。证明如下：

考虑加上 $n$ 的位置集合为 $S$，我们找到 $x<y$ 且 $P_x>P_y$，同时 $S$ 包含 $x$ 且不包含 $y$ 的所有 $(x,y)$，再找出其中 $P_x-P_y$ 最小的一对，可以证明此时从 $S$ 中删去 $x$ 并加入 $y$ 一定更优，具体见下图：

图中横坐标为 $i$，纵坐标为 $P_i$（下同），修改即为从两个红点变成两个黑点。我们分别分析修改后的变化量：

• 纵坐标大于 $P_x+n$ 和小于 $P_y$ 的部分：贡献不变。
• 第 $1$ 部分：不存在点，若存在 $(k,P_k)$ 则 $P_x-P_k$ 更小，$y$ 不合法。
• 第 $2$ 部分：不存在点，若存在 $(k,P_k+n)$ 则 $P_k-P_y$ 更小，$x$ 不合法。
• 剩余部分：分别与红点和黑点分析逆序对可知 $3,5$ 贡献不变，$6,7$ 贡献为 $-1$，$4$ 贡献为 $-2$。
• 序列中 $P_x+n,P_y$ 变成了 $P_x,P_y+n$，逆序对减少 $1$。

以上贡献均非正，所以修改后一定更优，结论得证。

从这个结论出发，我们可推得以下两条：

• 若 $x<y$ 且 $P_x>P_y$，则如果给 $x$ 加，一定也给 $y$ 加。
• 若 $x<y$ 且 $P_x>P_y$，则如果不给 $y$ 加，一定也不给 $x$ 加。

所以若目前要给 $i$ 加，根据第一条所有 $j>i,P_j<P_i$ 的 $j$ 一定加过了（记数量为 $c_1$），根据第二条所有 $j<i,P_j>P_i$ 的 $j$ 一定还没加（记数量为 $c_2$），此时若 $i$ 是第 $k$ 个被加的，贡献即为 $f_i=c_1-c_2+(n-i)-(k-1)$，其中 $(n-i)-(k-1)$ 比较复杂，详见下图：

$n-i$ 为 $i$ 右边所有点，先要减掉已经额外计算的 $c_1$；另外 $c_3$ 中被选过的点还会保持 $P_j+n>P_i+n$，也要减去； 还有 $c_4$ 中被选过的点算贡献后变成了 $P_j+n,P_i$ 的逆序对，现在又变回了 $P_j+n,P_i+n$ 的顺序对，需要减去 $1$ 把贡献消去。注意到减去的三部分恰为已经加过的所有点，因此减去的值为 $k-1$。

可以发现 $c_1$ 和 $c_2$ 已经可以在求逆序对时顺便求出了，但还可以再做一些推导。显然有 $c_3=n-i-c_1$，则 $c_2=n-P_i-c_3=n-P_i-n+i+c_1=i-P_i+c_1$，所以有 $f_i=c_1-c_2+(n-i)-(k-1)=n+P_i-2i-(k-1)$。

注意到 $n-(k-1)$ 与 $i$ 的选择无关，所以把所有的 $i$ 按照 $P_i-2i$ 升序排序，枚举加的个数，选 $f$ 最小的若干个加，对所有个数取最小值即可。

另外其实需要 $i$ 的 $c_1$ 中所有点先于其自身被加，但是注意到这些 $j$ 满足 $j>i,P_j<P_i$，所以 $f_j<f_i$，一定先于 $i$ 被选了，所以做法没问题，时间复杂度 $O(n\log n)$。

这是提交记录。