AT_awtf2024_d 题解

KSCD_ · 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) 比较复杂，详见下图：