题解：AT_awtf2024_d Almost Bubble Sort

MurataHimeko · 2025-02-13 16:53:00 · 题解

转化成给每个 i 赋 b_i=0/1 的权值，b_i=1 代表 a_i 要加 INF，答案就是最终序列的逆序对数。考虑按照 a_i 从大到小赋值并确定在最终序列里的排名，每个时刻已经确定的排名都形如 ...000..111。

若 b_i=1，则将 i 插入最后一个 1 之前， 这同时意味着所有满足 j\gt i,a_j \lt a_i 的位置都会形成逆序对，因为最终序列中 i 之后不可能再插入新的数。同理，若 b_i=0，将 i 插入第一个 0 之前，i 与所有满足 j \lt i, a_i \lt a_j 的位置形成逆序对。

令 S 为 b_i=1 的 i 构成的集合。

这里有一个关键结论，\forall i \lt j, b_i=1,b_j=0 \rightarrow a_i \lt a_j。严格证明的话，找到最近的点对 i,j，使得 b_i=1,b_j=0, a_i \gt a_j，调整为 b_i=0,b_j=1，将 (x,a_x) 画在二维平面上，则 (i,a_i),(j,a_j) 为顶点向上/下/左/右画出的射线可以将平面划分成 9 个区域，因为 i,j 为最近点对，所以中间区域没有点。然后分别讨论其余 8 个区域内的点跟 i,j 形成的逆序对数变化量，四个角上的区域变化量为 0，剩下的区域也能分讨出变化量 \leq 0，可以证明是更优的。

于是可能的逆序对 (i,j) 共有 3 种情况：

1. a_i \gt a_j, b_i=0,b_j=0
2. a_i \gt a_j, b_i=1,b_j=1
3. a_i \lt a_j, b_i=1,b_j=0

令 f_i=\sum_{j=1}^{i-1} [a_j\gt a_i],g_i=\sum_{j=i+1}^{n} [a_j \lt a_i]。

根据题解第二段的内容，若 b_i=0，对逆序对数贡献 f_i，若 b_i=1，对逆序对数贡献 g_i。发现少算了情况 3，那么再令 b_i=1 时额外加上 n-i，这样会多算情况 2 和 a_i \lt a_j, b_i=1,b_j=1，也就是 \binom{|S|}{2}。因为贡献之间独立，于是一开始令 |S| 为 0，增量扩大 S，这样就能减掉 \binom{|S|}{2}。

复杂度 O(n\log n)。