Counting Inversions

• 기본적인 Inversion Counting문제. 버블 소트와 거의 동일한 문제이고 동일한 방법으로 풀면 된다. 풀이는 링크를 참조. 시간복잡도는 O(nlogn)
  • 버블 소트 과의 차이점은 n의 범위가 50만에서 100만으로 늘어난 것과, 좌표압축이 필요 없다는 점.
• 다만 n이 두배로 증가한것때문에 시간 제한이 굉장이 빡빡해졌다. 버블 소트에서 사용했던 코드로는 Python에서 TLE가 난다.
  • PyPy로 제출했을때, 머지소트로는 열심히 최적화해도 1036ms, teflib.fenwicktree.OrderStatisticTree 로는 944ms.
• 결국 최후의 수단을 사용.. OrderStatisticTree의 코드를 main함수 안에 복붙해서 제출한 결과 4060ms로 통과. (Pypy로는 480ms)
  • 정상적으로 라이브러리를 사용한 코드는 버블 소트 참고.

"""Solution code for "BOJ 10090. Counting Inversions".

- Problem link: https://www.acmicpc.net/problem/10090
- Solution link: http://www.teferi.net/ps/problems/boj/10090
"""


def main():
    n = int(input())
    nums = [int(x) for x in input().split()]

    answer = 0
    tree = [0] * n
    for num in reversed(nums):
        # answer += tree.count_less_than(num)
        r = num - 1
        while r >= 0:
            answer += tree[r]
            r = (r & (r + 1)) - 1
        # tree.add(num)
        while num < n:
            tree[num] += 1
            num |= num + 1

    print(answer)


if __name__ == '__main__':
    main()