転倒数

計算機科学および離散数学における列の転倒（てんとう、英: inversion）は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。 $inv (A) = # {(A_{i}, A_{j}) ∣ i < j and A_{i} > A_{j}}$

結合した列x+yの転倒数はそれぞれの転倒数fと頻度表cから求められる ACLPC L PAST4K

$f (x + y) = f (x) + f (y) + \sum_{i} \sum_{j} c (x, i) c (y, j) [i > j]$

フェニック木を使ってO(NlogN)で求められる python

init(N)
inv = 0
for a in seqs[i]:
    bit_add(a, 1)
    inv += bit_sum(N) - bit_sum(a)