스위치

• 기본적인 구간 업데이트 / 구간 쿼리 문제.
• Lazy propagation을 지원하는 세그먼트 트리를 이용해서 쉽게 풀수 있다.
• 기본적으로 구간합 쿼리이므로, 구간을 합칠때 필요한 함수는 add. 업데이트는 구간의 값을 {구간 크기 - 구간값}으로 바꾼다. 업데이트에 따로 파라메터가 필요하지는 않고, 두번 누적되면 업데이트가 취소된다.
  • teflib의 LazySegmentTree에서는 update_param을 None로 바꿔주면 레이지 값이 사라지도록 구현되어있다. 그점을 이용해서 구현했다.
• 초기화에 O(n)이 들고, m개의 쿼리는 각각 O(logn)에 처리된다. 총 시간복잡도는 O(n+mlogn)

"""Solution code for "BOJ 1395. 스위치".

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

import operator
import sys
from teflib import segmenttree


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    lazy_segtree = segmenttree.LazySegmentTree(
        [0] * N,
        merge=operator.add,
        update_value=lambda v, p, size: size - v,
        update_param=lambda param1, param2: None,
        should_keep_update_order=False)
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 0:
            _, S, T = query
            lazy_segtree.range_update(S - 1, T, True)
        else:
            _, S, T = query
            print(lazy_segtree.query(S - 1, T))


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.LazySegmentTree