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)ほどの影響を受けなかったのかもしれない
でもこのアプローチはこれくらいまでかなあ

やっぱり挿入ソートベースじゃダメなのか

それともぜんぜん違うやり方が必要なのか