転倒数

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