가로 블록 쌓기

• 구간 업데이트와 구간 쿼리로 처리되는 문제. 여기에 좌표압축이 추가된 문제.
• 어떤 구간에 블럭을 놓는 것은, 그 구간의 최대 높이 h를 구한 뒤, 그 구간의 높이를 h+1로 업데이트 하는 것으로 처리된다.
• 따라서 구간 최대값 쿼리, 구간 assignment 업데이트를 지원하는 lazy segment tree를 이용하면 된다.
• 좌표의 크기가 최대 1,000,000,000이므로, 좌표 압축이 필수적이다.
• 좌표압축을 해서구간의 크기를 O(n)으로 축소시키고 나면, 각각의 블럭을 처리하는 데에, O(logn)의 구간쿼리와 O(logn)의 구간업데이트로 처리가 가능하다. 결국 n개의 블럭을 처리하는 데에는 O(nlogn)이고, 좌표압축에 걸리는 O(nlogn)을 추가해도 전체 시간복잡도는 O(nlogn)이 된다.
• n<100,000 밖에 안되지만 레이지 세그트리 연산이 느려서인지 Python으로는 시간 초과가 발생했다. PyPy로 제출해서 1초정도에 통과.

"""Solution code for "BOJ 18407. 가로 블록 쌓기".

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

This code should be submitted with PyPy3. Python3 gets TLE.
"""

import sys
import itertools
from teflib import segmenttree


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

    pos_set = set(itertools.chain.from_iterable((D, D + W) for W, D in blocks))
    compress_map = {x: i for i, x in enumerate(sorted(pos_set))}
    segtree = segmenttree.LazySegmentTree(
        [0] * len(pos_set),
        merge=max,
        update_value=lambda x, v, size: v,
        update_param=max,
        should_keep_update_order=False
    )
    for W, D in blocks:
        beg = compress_map[D]
        end = compress_map[D + W]
        height = segtree.query(beg, end)
        segtree.range_update(beg, end, height + 1)

    print(segtree.query(0, len(pos_set)))


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.LazySegmentTree