文書の過去の版を表示しています。
転倒数
具体的な例でイメージすると、$\{3,10,1,8,5\}$ のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。
これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。
例の場合、$(3,1)(10,1)(10,8)(10,5)(8,5)$ の5つの組で、左にある数字が右より大きくなっているので、転倒数は5である。
実際にやってみると、
3 10 1 8 5 3 1 10 8 5 3 1 8 10 5 3 1 8 5 10 1 3 8 5 10 1 3 5 8 10
たしかに5回で並び替えられる。
転倒数の求め方
数列の各要素について、独立に考えることが出来る。
つまり、「自分より右にある、自分より小さな数の個数」を、全要素求めて足し合わせると、それが転倒数となる。
3→ 10 1 8 5 : 1 の 1つ
10→ 1 8 5 : 1,8,5 の 3つ
1→ 8 5 : なし
8→ 5 : 5 の 1つ
5→ : なし
1+3+1 = 5
また、「自分より左にある、自分より大きな数の個数」でも同じ事である。
3 10 1 8 ←5 : 10,8 の 2つ 3 10 1 ←8 : 10 の 1つ 3 10 ←1 : 3,10 の 2つ 3 ←10 : なし ←3 : なし
「自分より左にある、自分より大きな数の個数」を高速に求めるには、 Binary Indexed Tree を用いる方法が使われる。
BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造である。
- 数列$\{a_1,a_2,...,a_n\}$があり、最初、全ての要素は0である
- 以下の2つの要求を処理する
ADD(i, x): $a_i$に$x$を加算（$1 \le i \le n$）SUM(t): $a_1$から$a_t$までの合計を得る（$1 \le t \le n$）
これを用いて、以下のように算出する。
BITを用意
まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。
数列を先頭から順番に処理する
$i$ 番目（1-indexed）の項を $p_i$ とする。各項に付き、以下の2つの処理を行う。
BITに加算する
$ADD(p_i, 1)$（BITの $p_i$ の位置に、1を加算する）
自分より左にある自分より大きい数の個数を求める
先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。
自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$（BITで $1$～$p_i$ の和）を求めることで得られる。
逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ である。
数列の各要素につきこれを足し合わせることで、転倒数が得られる。
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
ppp = [3, 10, 1, 8, 5]
bit = Bit(16)
ans = 0
for i, p in enumerate(ppp):
bit.add(p, 1)
ans += i + 1 - sum(p)
print(ans)
