転倒数
簡単に言うと、長さ$ Nの数列$ A上で、ある要素よりも右にある要素でありながら、その要素より小さいもの = ある要素よりも左にある要素でありながら、その要素より大きいもの の総数である。
バブルソートを掛けたときの swap 回数と等しくなるので、そういった言い方もされる。
厳密に述べる。
長さ$ Nの数列$ Aについて、
互いに相異なる$ 1以上$ N以下の整数組$ i, jであって$ A_i > A_jを満たすような$ i, jの組の種類数を、転倒数という。
例えば$ A = 3, 1, 5, 4, 2について考えると、
$ (i, j) = (1, 2), (1, 5), (3, 4), (3, 5), (4, 5)の場合にいずれも$ A_i < A_jが成り立つので、この数列$ Aの転倒数は$ 5である。
注意
以下に示す求め方の都合上、多くの問題では転倒数を求める対象の数列には値の重複がないことが保障されることが多い。
一応値が重複していても丁寧にやれば出来るが、以下は基本的に転倒数を求める対象の数列$ Aに値の重複がないものとして進める。
求め方
実際にバブルソートを掛けて間に合うなら、計算量$ Ο(N^2)で求めることが出来る。
code:c++
// 長さ n の数列が配列 a にあるとする。
int inversion = 0;
for(int i = 0; i < n - 1; i++) {
for(int j = 1; j < n; j++) {
inversion++;
}
}
}
// inversion に転倒数が求められている。
だが、大抵の場合転倒数を求める操作は$ N \leq 2 \times 10^5 とかで要求されるので、バブルソートでは全く間に合わない。
より高速な求め方
長さ$ Nの数列$ Aの転倒数を求めることを考える。
まずは、幾つかの条件を今まで述べた形とは少し異なる言い方にする。
互いに相異なる$ 1以上$ N以下の整数組$ i, jであって$ A_i > A_jを満たすような$ i, jの組
これは
ある$ iについて、$ 1 \leq j \lt iを満たす$ jであって、$ A_j > A_i
といったように、右側の要素を主軸にする。すると、
ある値について、それより左側にあるのに「ある値」より大きいような値の個数
の数え上げになる。
更に「より大きい」というのを直接扱うのではなく、
「今まで見てきた値の個数」から「ある値未満である値の個数」を引く
ことによって、間接的にそれを求める。
ただし、$ |A_i - A_j| \leq 10^{18} (1 \leq i, j \leq N)であるような場合などは座標圧縮を行う必要があるので注意。逆に、座標圧縮をしても各要素の大小関係までは失われないことに着目すると、転倒数を求めるための時間計算量は、対象となる数列の各要素についての定義域に関わらず$ Ο(N \log N)となる。 code:cpp
/**
* AtCoder::fenwick_tree を想定しています。
* 変数の状態に関してはバブルソートの例と同様。
* また、a の各要素は 0 以上 n-1 以下とします。
*/
ll inversion = 0;
fenwick_tree<ll> fwt(n);
for(int i = 0; i < n; i++){
inversion += i - fwt.sum(0, ai); }
例題