사용자 도구

사이트 도구


ps:problems:boj:10090

Counting Inversions

ps
링크acmicpc.net/…
출처BOJ
문제 번호10090
문제명Counting Inversions
레벨플래티넘 5
분류

Inversion Counting

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
사용한 언어Python
제출기록153496KB / 4060ms
최고기록4060ms
해결날짜2021/05/26

풀이

  • 기본적인 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()

토론

댓글을 입력하세요:
M Q R W Q
 
ps/problems/boj/10090.txt · 마지막으로 수정됨: 2021/07/31 15:51 저자 teferi