数列における転倒数を a_i > a_j (i < j)である(i, j)の組の数と定義する。例えば{2, 1, 4, 3}ならば(i, j) = (1, 2), (3, 4)で2である。
転倒数性質と求め方
バブルソートの交換回数は、転倒数と同じである。実際、バブルソートの隣り合った数字の交換を1回行うことで、ほかのペアに影響を与えず、互いに交換したペアだけ転倒数の条件を満たさなくなることからわかる。
これは蟻本でより詳しく解説されてる。
これは蟻本でより詳しく解説されてる。
実際の転倒数を求めるとき、大体数列の要素は10^5の定数倍までである。なぜならば、データ構造を利用して高速で求められるからである。
愚直に計算するとO(n^2)となるが、
愚直に計算するとO(n^2)となるが、
cntという配列を用意し、数字Aが現われてたらcnt[A]++する。
そしてAに対応する転倒数を求める際に、cnt[A+1]~cnt[n_max]の和を求めそれを転倒数として加算する。
これを数列の前から順に行う。
そしてAに対応する転倒数を求める際に、cnt[A+1]~cnt[n_max]の和を求めそれを転倒数として加算する。
これを数列の前から順に行う。
ARC101D - Medians of Medians(700)-転倒数への帰着
中央値と二分探索ARC101Dの続き。
この問題のように、大きいか小さいかの二通りの状態しか必要がない、区間への計算場合は
大きい->+1 小さい->-1と置換して、累積和をとれば、和が0以上の区間を調べればよい(この問題)。
このとき、和が0以上ということは、
大きい->+1 小さい->-1と置換して、累積和をとれば、和が0以上の区間を調べればよい(この問題)。
このとき、和が0以上ということは、
{区間の終わり - 区間の初め > 0 つまり
区間の終わり > 区間の初め
}
となる。これは転倒数のアルゴリズムの簡単な応用でとけるのでオーダーは落とせた。
区間の終わり > 区間の初め
}
となる。これは転倒数のアルゴリズムの簡単な応用でとけるのでオーダーは落とせた。
