테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 화려한 마을 ======

===== 풀이 =====
  * [[ps:세그먼트 트리#lazy propagation]]를 이용해서 푸는 구간 업데이트 + 구간 쿼리 문제.
  * 원래 구간에서 [[ps:구간 쿼리#서로 다른 수의 갯수]]를 찾는 것은 기본적으로 업데이트가 있을 때에는 효율적으로 처리하기 어려운 종류의 쿼리이다.
  * 그러나 이 문제에서는 사용할 색의 갯수가 매우 작기 때문에, 각각의 노드에 그 노드가 관리하는 구간 내에 존재하는 색의 목록을 모두 저장하고 있는 것이 가능하다. 이렇게 하면 구간을 합치는 것도 O(T)에 처리 가능하고, 색 목록을 bitmask를 사용해서 저장한다면 단순한 or연산이면 된다.
  * 업데이트 연산은 단순한 assignment 연산이 된다.
  * [[ps:세그먼트 트리#lazy propagation]]에서 사용한 노테이션대로, f,g,h 를 정의하면 아래처럼 된다.
    * f(x, y) = x|y.
    * g(x, c, size) = c
    * h(c1, c2) = c2
  * 구간 쿼리를 해서 f값을 얻은 다음, 그 안에 켜져있는 비트 수를 세면 된다.
  * 세그먼트 트리를 구축하는 데에 O(n), m개의 쿼리를 각각 O(t*logn)에 처리하는 데에 O(m*t*logn), 합쳐서 O(n+m*t*logn)이다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12895. 화려한 마을".

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

import operator
import sys
from teflib import segmenttree


def main():
    N, T, Q = [int(x) for x in sys.stdin.readline().split()]    
    lazy_segtree = segmenttree.LazySegmentTree(
        [1] * N,
        merge=operator.or_,
        update_value=lambda value, param, size: param,
        update_param=lambda param1, param2 : param2)  
    for _ in range(Q):
        query = sys.stdin.readline().split()
        if query[0] == 'C':
            x, y, z = [int(x) for x in query[1:]]
            lazy_segtree.range_update(x - 1, y, 1 << (z - 1))
        else:
            x, y = [int(x) for x in query[1:]]
            ret = lazy_segtree.query(x - 1, y)
            print(bin(ret).count('1'))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:segmenttree#LazySegmentTree|teflib.segmenttree.LazySegmentTree]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}