算法
(分块) $O(n\sqrt{n}\log n)$
先把这个长度为 $n$ 的排列分成 $m$ 块。
如果交换的两个位置在同一个块内。
那么它们对其他块并没有影响。
只要暴力交换,计算一下块内的逆序对数变化了多少即可。
时间复杂度 $O(m)$
如果交换的两个位置不在同一个块内。
比如交换的两个位置是 $x$ 和 $y$。
那么就需要直到在 $[x + 1, \cdots, y - 1$中有几个数大于/小于 $a[x]$
以及在 $[x + 1, \cdots, y - 1]$ 中有几个数大于/小于 $a[y]$
枚举中间的每个块,块内二分即可。
时间复杂度为 $O(n / m \log m)$
取 $m = \sqrt{n}$ 左右,可以使总的时间复杂度在 $O(n\sqrt{n}\log n)$