cs

交换两个成逆序对的数，必然会减少总逆序对数

$x_1 … x_i … x_j … x_n，\ x_i > x_j$

交换成

$x_1 … x_j … x_i … x_n$

只有和 $x_i \ x_j$ 有关的 pair 才会变。

$[1, i)$ 和 $(j, n]$ 的都不用考虑，其与 $x_i \ x_j$ 的相对位置不变。

考虑 $(i, j)$ 内的下标 $p$ ，

  1. 若 $(x_i, x_p)$ 原本构成逆序，则交换后不再是逆序
  2. 若 $(x_i, x_p)$ 原本不构成逆序，则交换后要么变逆序，要么仍然不是逆序(二者相等)
  3. 若 $(x_j, x_p)$ 原本构成逆序，则交换后不再是逆序
  4. 若 $(x_j, x_p)$ 原本不构成逆序，则交换后要么变逆序，要么仍然不是逆序(二者相等)

这样并不好看出来结论，但是可以看出如果有元素相等，逆序对总数是更不容易增加的，所以以下只需证明序列元素各不相等的情况下一定减少。

从 $x_p$ 来看，成对考虑 $ip 和 pj$ ：

  1. 若 $x_p < x_j < x_i$ ，$(x_i, x_p)是 (x_p, x_j)否$ -> $(x_j, x_p)是 (x_p, x_i)否$ ，总逆序对数不变
  2. 若 $x_j < x_p < x_i$ ，$(x_i, x_p)是 (x_p, x_j)是$ -> $(x_j, x_p)否 (x_p, x_i)否$ ，总逆序对数减小
  3. 若 $x_j < x_i < x_p$ ，$(x_i, x_p)否 (x_p, x_j)是$ -> $(x_j, x_p)否 (x_p, x_i)是$ ，总逆序对数不变

没有原本 $(x_i, x_p) \ (x_p, x_j)$ 是否否的情况，若 $x_i \le x_p$ ，则由于 $x_i > x_j$ ，一定有 $(x_p, x_j)$ 是逆序的。

以上3种情况，可以看出总逆序对数单减，再加上 $(x_i, x_j)$ 这对逆序对确实地被消除了，总逆序对数一定严格单减。

不过，相邻逆序对数却不一定减少，例如 [3 1 2] 变成 [1 3 2] ，相邻逆序对数没变，都是1。

扩展结论：

如果 $(x_i, x_j)$ 相邻且逆序，交换相邻的二者，总逆序对数一定减1 （因为中间没有p，一定是减1）。

相邻逆序对数不一定减少。[3 1 2] 变成 [1 3 2] 不变；[2 1 3] 变成 [1 2 3] 减1；[4 6 3 5] 变成 [4 3 6 5] 加1 （构造思路：6 3 变 3 6，然后构造3和6的左右逆序，且原本不逆序）；

可以证明：增加/减少的话，变化值最大为1。增加明显最多+1，且有例子可以达到。减少的话，不妨设为 * 6 3 * 这个形式，* 6 和 3 * 都不可能从逆序变为非逆序，所以最多-1。

03.List.pdf P57:

img

插入排序一轮，相邻逆序对数一定不变或减少

假设插入排序前部为 $[0, i]$，后部为 $[i+1, n)$

若 $a[i + 1] \ge a[i]$，此轮不需操作，相邻逆序对数不变

若 $a[i + 1] < a[i]$，操作之后原 $a[i], a[i + 1]$ 的逆序对没了，可能多出来的逆序对为 $a[i+1], a[i+2]$ ，最多维持不变

序列的值各不相同，交换两个数，总逆序对数的奇偶性会变一次

… x … y …

x y 交换，只有中间的数组合 x y 的逆序对会变，考虑这一部分

  1. x的逆序对，原本x 和 (x, y) 之间的元素产生逆序，记这部分为p，剩余部分为q，p + q = y - x - 1。 则交换后，与x构成逆序对的变成q了
  2. y同理，由p’变成q’了

二者相加，p + q + p’ + q’ = (y - x - 1) * 2，再加上 x y 交换产生的逆序对，合计为奇数，说明交换前后一定一奇一偶。

或者这样来证明：把 x y 的交换过程视作 y 与左边的元素一步步交换（路径无关性），直到变成 y x … ，然后 x 再一步步交换到右边。每次交换相邻的不等值元素，总逆序对数一定加1或减1（改变一次奇偶性）。 总交换次数为 $2 * dis(x, y) - 1$ 为奇数，则最后一定改变奇偶性。

也可以像上面的方式那样分析。交换的两个数原本若成逆序就是上面的情况，case2的变化一定是偶数次，再算上 $x y$ 的逆序变化，逆序变化次数总数一定为奇数。若交换的两个数原本不成逆序，同理分析。

但是如果序列有重复值，则结论不成立。例如 [6 3 3] 变成 [3 3 6] 总逆序对数从 2 变成 0，奇偶性没变。有重复值不成立的原因在于：p和q的对立性不满足了，可能交换前不逆序，交换后仍然不逆序。

用上面的分析方式来分析有相等元素的情况，$x_i \ x_p \ x_j$，若 $x_i = x_j$，交换后总逆序对数不变；若 $x_i < x_j$，以中间有元素 $x_p$ 满足 $x_i < x_p = x_j$ 为例，交换后对于 $i, p, j$，逆序对数变化次数为 $1$ (因为 $x_p = x_j$，变化次数与上面的 case2 有了区别，可以是奇数了)，所以，视此类 $x_p$ 的个数，总逆序对数变化可以是奇数，可以是偶数；$x_i > x_j$ 的情况同理分析。

若序列共有 $I$ 个逆序对，则插入排序的比较次数为 $O(I)$

同写在插入排序中的结论。

统计总逆序对数

蛮力二重循环/冒泡排序(冒泡排序的交换次数等于总逆序对数)，都需要 $O(n^2)$ 时间。

借助归并排序或者认为是线段树的分治思路，只需 $O(nlogn)$ 时间。见count_inversions.cpp。