転倒数 (inversion number) とは? 数列 a = {a_0, a_1, a_2 ... a_n-1 } が与えられたとき, i < j かつ a_i > a_j を満たす (i, j) の組の個数を転倒数または反転数という. たとえば a = {3, 1, 5, 4, 2} のとき, i < j かつ a_i > a_j となっている組は, (3…

転倒数 アルゴリズム