転倒数

値を座標圧縮し、左から順に「それより前にある、自分より大きい値の個数」を BIT（Fenwick Tree）で数えて足します。

• inversion_count(a): 列 $a$ の転倒数（ $i < j$ かつ $a_i > a_j$ となる組 $(i, j)$ の個数）。値は大小を比べられれば何でもよい。 $O(N \log N)$

隣り合う 2 つの要素の交換をくり返して $a$ を昇順に並べるとき、交換の最小回数は転倒数に等しくなります。

コード

def inversion_count(a):
    # i < j かつ a[i] > a[j] となる組 (i, j) の個数
    vals = sorted(set(a))
    idx = {x: i + 1 for i, x in enumerate(vals)}
    m = len(vals)
    bit = [0] * (m + 1)
    res = 0
    for i, x in enumerate(a):
        k = idx[x]
        # これまでに出てきた x 以下の値の個数を数え、残りを足す
        j = k
        s = 0
        while j:
            s += bit[j]
            j -= j & -j
        res += i - s
        while k <= m:
            bit[k] += 1
            k += k & -k
    return res