题解：AT_awtf2024_d Almost Bubble Sort

转化成给每个 $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$ 种情况：

令 $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)$。