ALDS1_5_D: The Number of Inversions (続き)
あるいは挿入ソート的なやりかただけど二分探索してみるとか
でも挿入するのにO(n)かかるとあんまり変わらないかもしれない
やってみた
from bisect import bisect_left
def count_inversion(A):
cnt = 0
for i in reversed(range(len(A) - 1)):
j = bisect_left(A, A[i], i + 1, len(A))
cnt += j - i - 1
tmp = A[i]
del A[i]
A.insert(j - 1, tmp)
return cnt
def main():
n = int(input())
A = [int(x) for x in input().split()]
print(count_inversion(A))
main()
データ数100000はクリアできたけど200000でTLE
しかもbisect使って
挿入は組み込みだからO(n)ほどの影響を受けなかったのかもしれない
でもこのアプローチはこれくらいまでかなあ
やっぱり挿入ソートベースじゃダメなのか
それともぜんぜん違うやり方が必要なのか