from 第四回 アルゴリズム実技検定 PAST4K K - 転倒数
- 考えたこと
- 公式解説
- 方針は良い
- 同じ列が繰り返し使われる時に毎回フェニック木で転倒数を求めていたのがよくない
- 転倒数と頻度表を前処理すべきだった
- 列の長さの和が小さく抑えられているのは、前処理でフェニック木を使うのはTLEしないが、クエリのたびに使うとクエリが長い列ばかり選ぶ場合があってNGという意図
- AC python
def solve(K, seqs, Q, BS):
MOD = 10 ** 9
N = 20
invs = []
freqs = []
for i in range(K):
init(N)
freq = [0] * 21
inv = 0
for a in seqs[i]:
bit_add(a, 1)
inv += bit_sum(N) - bit_sum(a)
freq[a] += 1
invs.append(inv)
freqs.append(freq)
ret = 0
freq = [0] * 21
for b in BS:
ret += invs[b - 1]
f = freqs[b - 1]
for i in range(1, 21):
for j in range(i + 1, 21):
ret += f[i] * freq[j]
for i in range(1, 21):
freq[i] += f[i]
ret %= MOD
return ret