시장 선거 포스터

• 이 문제를 푸는 방법은 다양하다.
• 가장 나이브한 방법은, 벽 전체에 대응되는 배열을 만들어서, [l,r] 구간을 덮는 포스터를 추가할때마다 배열의 [l,r] 구간을 그 포스터의 번호로 업데이트해주는 것이다. 모든 업데이트가 끝난 뒤에, 배열에 저장된 서로 다른 값들의 갯수를 계산해주면 된다. 실제 좌표를 그냥 쓰는 것은 좌표 범위가 너무 커서 안되지만, 좌표 압축을 해서 배열 크기를 O(n)으로 줄이면, 총 O(n^2)이고, 이것으로도 통과된다. (CPython으로는 힘들고 Pypy로 제출해야 하는것 같다)
• 이 과정을 좀더 효율적으로 하기 위해서 바로 떠오르는 것은 lazy segment tree이다. 포스터를 덮는 것을 레인지 업데이트로 처리해주고, 마지막에 구간을 전부 훑으면서 서로 다른 값들의 갯수를 계산해주면 O(nlogn)에 처리할수 있다. 물론 좌표압축은 당연히 필요하다.
  • 서로 다른 값들의 갯수를 찾는 것은 여러가지 다른 방법들로 대체할수 있지만, 어차피 레인지 업데이트는 공통적으로 필요하기 때문에 lazy segment tree를 안 쓸수는 없다. 예를들면 포스터를 모두 붙인 뒤에, 각 포스터가 보이는 구간이 있는지 하나씩 체크할수도 있다. 어떤 포스터가 보이는지를 찾으려면 그 포스터에 대응하는 구간의 range min 쿼리를 날려서, min값이 그 포스터의 번호와 같으면 포스터가 보인다고 찾을수 있다.
• 같은 O(nlogn)이긴 하지만, 좀더 간단한 자료구조만으로 처리하려면 스위핑으로 접근할수 있다. 포스터의 왼쪽 좌표와 오른쪽 좌표들을 모아서 정렬시키고 스위핑하면서, 현재 붙어있는 포스터들의 목록을 관리해주면 된다. 각 좌표들에서 포스터를 추가/삭제해줘야 하고, 그때마다 붙어있는 포스터 중에서 가장 나중에 붙은 포스터를 찾아주면 되는데, 이것은 우선순위 큐를 써서 쉽게 처리할수 있다. 임의 원소 삭제를 지원하는 힙#원소 삭제가 가능하도록 약간의 처리가 필요하긴 하다. 시간복잡도는 여전히 O(nlogn)이지만 더 간단하고, 좌표압축도 따로 필요 없다.
• 실수하기 쉬운 부분은 인풋에서 포스터의 범위로 주어지는 값은 좌표 기준이 아니라 벽 조각의 번호 기준이라는 것. l==r 이더라도, 덮는 영역이 0이 아니라 한개의 벽 조각은 덮는것이라는 것을 고려해서 코드를 짜야한다.

"""Solution code for "BOJ 2370. 시장 선거 포스터".

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

Tags: [sweeping]
"""

import collections
import sys
from teflib import priorityqueue


RIGHT = 0
LEFT = 1


def main():
    n = int(sys.stdin.readline())
    events_by_coord = collections.defaultdict(list)
    for poster_no in range(n):
        l, r = [int(x) for x in sys.stdin.readline().split()]
        events_by_coord[l].append((LEFT, poster_no))
        events_by_coord[r + 1].append((RIGHT, poster_no))

    visible_posters = set()
    heap = priorityqueue.UpdatableHeap()
    for _, events in sorted(events_by_coord.items()):
        for type_, poster_no in events:
            if type_ == LEFT:
                heap.push(-poster_no)
            else:
                heap.delete(-poster_no)
        if heap:
            visible_posters.add(heap.top())

    print(len(visible_posters))


if __name__ == '__main__':
    main()

• Dependency: teflib.priorityqueue.UpdatableHeap