북서풍

• 기본적인 Inversion Counting 문제.
• 좌표의 범위가 크므로 좌표 압축이 필요하다
• 시간 복잡도는 O(nlogn)..인데 테스트 케이스가 여러개이다.
• 테스트 케이스의 갯수가 주어지지 않는데 수가 적지는 않은것 같다. n의 범위가 75000이하밖에 안되는데도 Python으로는 시간이 상당히 빡빡하다. 처음에는 Python으로는 포기하고 PyPy로 제출했었는데. 그 뒤에 python3으로 통과한 사람이 생긴 것을 보고서 나도 조금 더 최적화를 하다보니 아슬아슬하게 시간 내에 들어왔다. 좌표 압축하는 루틴을 작성할때 보통은 가독성을 위해서 set을 이용해서 중복값을 제거하거나, itertools.groupby를 써서 중복값을 처리하거나 하는 방식으로 해왔는데, 이번에는 그냥 수작업으로 풀어서 처리했다.

"""Solution code for "BOJ 5419. 북서풍".

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

import operator
import sys
from teflib import fenwicktree


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        points = [[int(x) for x in sys.stdin.readline().split()] 
                  for _ in range(n)]

        points.sort(key=operator.itemgetter(1))
        compressed_y = 0
        prev = points[0][1]
        for point in points:
            if point[1] != prev:
                prev = point[1] 
                compressed_y += 1
            point[1] = compressed_y
        answer = 0
        fenwick = fenwicktree.FenwickTree(n)
        for _, y in sorted(points, key=lambda p: -p[0]):
            answer += fenwick.query(0, y + 1)
            fenwick.update(y, 1)

        print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree