사용자 도구

사이트 도구


ps:problems:boj:11012

Egg

ps
링크https://www.acmicpc.net/problem/11012
출처BOJ
문제 번호11012
문제명Egg
레벨플래티넘 1
분류

구간 쿼리

시간복잡도O(T(n+m)(logk + log(n+m)))
인풋사이즈T<=20, n<=10,000, n<=50,000, k<=100,000
사용한 언어Python
제출기록53832KB / 6624ms
최고기록6624ms
해결날짜2021/04/28
태그

39단계

풀이

  • 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()

토론

댓글을 입력하세요:
B Z V V O
 
ps/problems/boj/11012.txt · 마지막으로 수정됨: 2021/05/05 16:34 저자 teferi