Rectpoints

• 비교적 전형적인 테크닉들을 사용하는 문제
• 우선 1차원에서 생각해보자. y좌표가 모두 동일하다고 가정해본다면, 1차원에서 점을 가장 많이 포함하는 크기 w짜리 구간을 찾는 문제가 된다. 이것을 살짝 변환하면 구간이 가장 많이 겹치는 점을 찾는 문제로도 바꿀수 있다. x에 있는 점을 [x, x+w] 구간으로 바꿔서 생각해서 구간이 가장 많이 겹치는 점 x0를 찾았다고 하자. 이 답을 원래 문제 기준으로 다시 바꾸어 생각하면 [x0-w, x0]이 점을 가장 많이 포함하는 구간이 된다.
• 구간이 가장 많이 겹치는 점을 찾는 방법들은 Maximum overlapping intervals 에서 설명했다. 업데이트와 쿼리를 온라인으로 처리해야 하면 lazy segment tree를 써야 하고, 그렇지 않다면 그냥 정렬 후 스위핑을 쓰면 된다.
• 이제 이것을 2차원으로 확장해주면 된다. x축과 y축에 모두 레이지 세그트리를 적용하는 2차원 레이지 세그트리도 불가능하지는 않겠지만.. 한쪽은 정렬후 스위핑으로 처리하고, 그러면 다른 축은 온라인 처리가 강제되므로 그쪽에만 레이지 세그트리를 적용하는것이 당연한 발상이다..
• 각 점마다, x_i에 점추가 이벤트, x_i+w 에 점삭제 이벤트를 만들어서, 이벤트들을 모아서 정렬한 후에 하나씩 처리해준다. 점 추가 이벤트에서는 [y_i, y_i+h] 구간에 1씩 더해주고, 점 삭제 이벤트에서는 [y_i, y_i+h] 구간에서 1씩 빼준다. 그리고 점 추가 이벤트마다 전체 구간에 대해 max query를 날려서, 최댓값을 갱신해주면 끝.
• 이때, 세그트리를 쓰는 y축 쪽은 그대로 쓰려면 좌표 범위가 10^8이라서 메모리 초과가 나게 된다. 좌표 압축을 통해서 O(n)으로 압축해주면, 메모리 O(n), 업데이트와 쿼리의 시간복잡도 O(logn)에 처리된다. x축 기준 정렬, y축 좌표압축, 세그트리로 O(n)개의 업데이트/쿼리 처리를 모두 포함한 시간 복잡도는 O(nlogn)이다
  • 그래도 작업이 많아서 python으로는 시간 초과가 나고, pypy로 해도 거의 2200ms나 걸려서 통과된다.

"""Solution code for "BOJ 24320. Rectpoints".

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

Tags: [lazy segtree]
"""

import sys
from teflib import segmenttree

ADD = 0
REMOVE = 1


def main():
    N, w, h = [int(x) for x in sys.stdin.readline().split()]
    events = []
    y_coords = set()
    for _ in range(N):
        x, y = [int(x) for x in sys.stdin.readline().split()]
        y_coords.add(y)
        y_coords.add(y + h + 1)
        events.append((x, ADD, y))
        events.append((x + w, REMOVE, y))

    size = len(y_coords)
    compress_map = {y: i for i, y in enumerate(sorted(y_coords))}
    segtree = segmenttree.LazySegmentTree(
        [0] * size,
        merge=max,
        update_value=lambda v, p, _: v + p,
        update_param=lambda p1, p2: p1 + p2,
    )
    answer = 0
    for _, type_, y in sorted(events):
        beg, end = compress_map[y], compress_map[y + h + 1]
        if type_ == ADD:
            segtree.range_update(beg, end, 1)
            answer = max(answer, segtree.query(0, size))
        elif type_ == REMOVE:
            segtree.range_update(beg, end, -1)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.LazySegmentTree