転倒数
Abstract
長さ$ Nの数列$ A = (a_i)_{i=1}^{N}で, $ i < jかつ$ a_i > a_jであるような組$ (i, j)の個数$ \mathop{\mathrm{inv}}(A)を転倒数 (inversion number) という. 計算量は$ O(N \log N)timeで済む.
Explanation
分割統治法による解法
マージソートを実際にやることで転倒数を求める.
数列$ Aの長さが1のときは$ \mathop{\mathrm{inv}}(A) = 0.
数列$ Aを半分にして, $ A_1 = (a_i)_{i = 1}^{\lfloor N/2 \rfloor}と$ A_2 = (a_i)_{i=\lfloor N/2 \rfloor + 1}^{N}をつくる.
次が成立する: $ \mathop{\mathrm{inv}}(A) = \mathop{\mathrm{inv}}(A_1) + \mathop{\mathrm{inv}}(A_2) + \left|\{ (i, j) \mid a_i \in A_1, a_j \in A_2, a_i > a_j \}\right|
右辺第3項については, マージソートしながら計算すればよい.
計算量はマージソートにかかる$ O(N \log N)timeである.
BITによる解法
各$ jに対して, $ i < jかつ$ a_i > a_jとなる$ iの個数を$ t_jとし, $ a_i \le a_jとなる$ iの個数を$ t_j'と定めると
$ \mathop{\mathrm{inv}}(A) = \sum_{j=1}^{N} t_j = \sum_{j=1}^{N} (j - t_j' - 1)
である. $ t_jの代わりに$ t_j'を求めてもよいことがわかる.
配列$ B を用意し, $ j = 1, 2, \dots, N の順に$ B[a_j] に1を足していくことにする. $ j = k の更新が終わった時点で, $ B[v] には$ a_1, \dots, a_kのうち値が$ vとなるものの個数が格納されていることになる. このとき,
$ t_{k+1}' = \sum_{v < a_{k+1}} B\lbrack v \rbrack
上のような配列$ B をつくると, $ A に含まれない値$ v については常に$ B[v] = 0 となり無駄だが, 座標圧縮を行えば$ O(N)spaceで済む. 座標圧縮の前処理は$ O(N \log N)timeで, $ t_j'の計算は全部で$ O(N \log N)timeで済む. 以上より, 計算量は$ O(N \log N)timeである.
Implementation
分割統治法による解法
Input
長さ$ Nの数列 A
Output
転倒数 count
ソート済みの数列 sorted_A
Time complexity
$ O(N \log N)time.
code:python
def inversion_number(A):
count = 0; n = len(A)
sorted_A = []
if n > 1:
A1, A2 = A:n // 2, An // 2: # len(A1) = n // 2, len(A2) = n - (n // 2) c1, A1 = inversion_number(A1)
c2, A2 = inversion_number(A2)
count += c1 + c2
j, k = 0, 0
for i in range(n):
if k == len(A2): sorted_A += A1j:; break elif j == len(A1): sorted_A += A2k:; break elif A1j <= A2k: sorted_A.append(A1j); j += 1 else: sorted_A.append(A2k); k += 1; count += n // 2 - j else:
sorted_A = A
return count, sorted_A
BITによる解法
Input
長さ$ Nの数列 A
Output
転倒数 count
Time complexity
$ O(N \log N)time.
code:python
class BIT:
def __init__(self, n, init=None):
self.size = n
if init is None:
self.bit = 0 * (n + 1) # don't use bit0 else:
for i in range(1, n):
def sum(self, i):
'''
Calculate bit1 + ... + biti '''
S = 0
while i > 0:
i -= i & -i
return S
def add(self, i, x):
'''
'''
assert i > 0
while i <= self.size:
i += i & -i
def coord_compress(A):
B = {a: i for i, a in enumerate(sorted(set(A)))}
def inversion_number(A):
inv = 0
bit = BIT(len(A))
for i, x in enumerate(coord_compress(A)):
inv += i - bit.sum(x+1)
bit.add(x+1, 1)
return inv
Verification
References