Egg

• 2차원 좌표들을 정렬하여 1차원 배열로 만드는 기법을 사용하자.
• 그렇게 하면, 사각형 영역 안에 들어있는 점의 갯수를 묻는 쿼리가 [l:r]의 구간 내의 원소중에서 [b,t] 사이에 있는 것의 갯수를 묻는 구간쿼리 문제로 쉽게 변환된다
• [b,t] 범위에 있는 값의 갯수는 {t+1보다 작은 값의 갯수} - {b보다 작은 값의 갯수} 니까 구간 rank 쿼리로 처리된다.
• 구간 rank 쿼리 에서 설명한대로, 오프라인 쿼리를 이용해서 푸는 것이 가장 효과적이다. 이 경우도 똑같이 적용하면 마치 스위핑 알고리즘을 쓰는 것처럼 처리된다.
• 좌표의 범위가 10^5으로, 점의 갯수 10^4과 큰 차이가 안나므로 굳이 좌표 압축을 사용할 필요가 없다.
• 또, 각 쿼리의 결과를 출력하는 것이 아니라, 쿼리 결과들의 합을 출력하는 것이라서, 쿼리 순서를 기억할 필요도 없어서 코드가 더 간단해진다.
• 실제 구현은 점을 추가하는 것과 쿼리를 처리하는 것을 다 같은 이벤트로 묶어서 전체를 스위핑하는 느낌이로 처리했고, O(n+m)개의 이벤트를 처리 하는데에 O((n+m)log(n+m)) 이 걸리고, 각 이벤트를 처리하는 것은 점을 추가하거나 rank를 계산하는 것 둘다 O(logk)가 걸린다 (k는 좌표값의 범위). 합치면 O((n+m)log(n+m) + (n+m)logk) = O((n+m)(logk + log(n+m))) 이 된다.

"""Solution code for "BOJ 11012. Egg".

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

import sys
from teflib import fenwicktree

LEFT = 0
EGG = 1
RIGHT = 2


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        events = []
        n, m = [int(x) for x in sys.stdin.readline().split()]
        for _ in range(n):
            x, y = [int(x) for x in sys.stdin.readline().split()]
            events.append((x, EGG, y))
        for _ in range(m):
            l, r, b, t = [int(x) for x in sys.stdin.readline().split()]
            events.append((l, LEFT, b, t))
            events.append((r, RIGHT, b, t))

        total_egg_count = 0
        max_y = max(event[-1] for event in events)
        y_coords = fenwicktree.OrderStatisticTree(max_y)
        for event in sorted(events):
            if event[1] == EGG:
                y = event[2]
                y_coords.add(y)
            else:
                b, t = event[2:]
                egg_count = (y_coords.count_less_than(t + 1) -
                             y_coords.count_less_than(b))
                if event[1] == LEFT:
                    total_egg_count -= egg_count
                else:
                    total_egg_count += egg_count

        print(total_egg_count)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.OrderStatisticTree