反転数 (the number of inversions)

概要

反転数は列 \(a_1, a_2, ..., a_N\) を隣接要素を交換しながらソートする時に必要な(最小)交換回数を表す。

単純にバブルソートで反転数を計算すると \(O(N^2)\) かかるが、BITを用いると \(O(N \log N)\) で計算できる。

計算量

\(O(N \log N)\)

実装

\(N\) と順列 \(a_1, a_2, ..., a_N (1 \le a_i \le N, a_i \not = a_j \text{ if } i \not = j)\) を受け取り反転数を計算する例

N = int(input())
*A, = map(int, input().split())

# BIT
data = [0]*(N+1)
def add(k, x):
    while k <= N:
      data[k] += x
      k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

ans = 0
for i, a in enumerate(A):
    # 自分より小さい要素がいくつ存在するかを計算
    ans += (N-1-i) - get(a)
    add(a, 1)
print(ans)