====== 북서풍 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}