여우가 정보섬에 올라온 이유

• Inversion Counting의 활용 문제이다.
• s.x < t.x < u.x이고 s.y > t.y < u.y인 세 원소쌍을 찾는 문제인데, x를 기준으로 정렬시켜 처리하면 i<j<k 이면서 Ai>Aj>Ak 인 세 원소쌍을 찾았던 불만 정렬과 거의 유사한 방식으로 해결할 수 있다.
  • u를 기준으로 봐서, 먼저 발생한 인버전중 y좌표가 현재 점보다 작은 것들을 세어주는 방법이 있다. 이것은 각 점을 저장하는 BST와, 2쌍 인버전을 저장하는 BST 두개가 필요하다.
  • t를 기준으로 봐서, 먼저 들어온 점들중 y좌표가 현재 점보다 큰 점들과, 나중에 들어오는 점들중 y 좌표가 현재 점보다 큰 점들을 각각 세어서 곱하는 방법이 있다. 이것은 x가 증가하는 순으로 한번 스캔하며 처리하고, 다시 x가 감소하는 순으로 스캔하는 두번의 스캐닝이 필요하다.
• 하지만, y를 기준으로 정렬시켜 처리하면 좀 더 쉽게 처리할 수 있다. t를 기준으로 보면서, 현재 점보다 먼저 들어온 점들중 x좌표가 현재 점보다 큰 점들과 작은 점들의 갯수를 각각 구해서 곱하면 된다. 한번의 스캐닝으로 처리 가능하고, x좌표가 현재 점보다 큰 점들을 O(logn)에 세고 나면, x좌표가 현재 점보다 작은 점을 세는 것은 O(1)에 가능하다. 전체 점의 수에서 x좌표가 큰 점의 수과 같은 점의 수를 빼면 된다.
• 구현은 펜윅트리를 BST 용도로 사용했고, 이를 처리하기 위해서 좌표들을 전부 양수가 되도록 이동시켰다. 좌표의 범위가 점의 최대 갯수의 2배밖에 안되므로 굳이 좌표압축까지 하는 것을 효율이 떨어질것 같아서, 그냥 최솟값이 0이 되도록 일정값을 더해주는 것으로 처리했다.
• 시간복잡도는, 좌표 정렬에 O(nlogn), n개의 점을 스위핑하면서 각각 O(logm)의 쿼리를 처리하므로, 총 시간 복잡도는 O(nlogn + nlogm) = O(nlogm)이다 (n은 점의 갯수, m은 좌표의 범위). 좌표압축을 했으면 O(nlogn)이 된다.

""""Solution code for "BOJ 17131. 여우가 정보섬에 올라온 이유"

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

import itertools
import operator
import sys
from teflib import fenwicktree

MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline())
    stars = []
    for _ in range(N):
        x, y = [int(x) for x in sys.stdin.readline().split()]
        stars.append((x, y))

    min_x = min(x for x, y in stars)
    fenwick = fenwicktree.FenwickTree(max(x for x, y in stars) - min_x + 1)
    answer = 0
    total_point_count = 0
    stars.sort(reverse=True, key=operator.itemgetter(1))
    for _, group in itertools.groupby(stars, key=operator.itemgetter(1)):
        compressed_x = [x - min_x for x, y in group]
        for cx in compressed_x:
            up_left_point_count = fenwick.query(0, cx)
            up_right_point_count = (total_point_count - up_left_point_count -
                                    fenwick.get(cx))
            answer += up_left_point_count * up_right_point_count
        for cx in compressed_x:
            fenwick.update(cx, 1)
            total_point_count += 1

    print(answer % MOD)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree