[백준/12895] 화려한 마을 (Python)

Problem : https://www.acmicpc.net/problem/12895

12895번: 화려한 마을

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:20:21

 

---

 

문제 설명

 

민호가 관리하는 천나라에는 N개의 집이 있다. 민호는 집을 쉽게 관리하기 위해 각각의 집을 1번, 2번, … N번으로 부르기로 했다.

어느 날 미적 감각에 눈을 뜬 민호는 특정 구간의 집들의 색들을 새롭게 칠하거나, 특정 구간의 집들에 존재하는 색의 수를 알고 싶어졌다.

작업은 다음과 같은 두가지로 이루어 진다.

“C x y z” : x번과 y번, 그리고 그 사이에 있는 모든 집을 z번 색으로 색칠한다.
“Q x y” : x번과 y번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다.
민호가 사용할 색의 종류는 (1번, 2번, … T번) 이라 하고 처음 모든 집은 1번으로 색칠되어 있다고 생각한다.

민호가 해야하는 작업을 시뮬레이션 해보는 프로그램을 작성하자.

 

입력 및 출력

 

입력

 

첫 번째 줄에 N, T, Q (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 30, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다. 각각 천나라에 존재하는 집의 개수, 사용할 색의 개수, 작업의 개수를 의미한다.

두 번째 줄부터 작업이 주어진다. 작업은 “C x y z” 또는 “Q x y” 둘 중에 하나의 형식으로 주어진다.

 

출력

 

작업이 “Q x y”일 때의 경우 x번과 y번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다.

 

입력 예시

 

2 2 4
C 1 1 2
Q 1 2
C 2 2 2
Q 1 2

 

출력 예시

 

2
1

 

 

---

 

풀이

 

느리게 갱신되는 세그먼트 트리를 사용해보자. 구간 업데이트 시 1. 모든 구간이 그 색으로 칠해지며 2. 이전 구간의 업데이트가 모두 덧씌워진다는 사실을 명심하자.

 

이 사실로부터 출발하면, T가 최대 30임을 다음으로 생각해보자. 즉 하나의 lazy 값은 하나의 색만을 저장해두면 되며, 우리의 색상 표현은 배열 등의 추가적인 메모리 소모 없이 비트마스킹으로 풀이 가능하다. 검색 쿼리는 비트마스킹 연산 결과 후 1의 개수를 출력하는 것으로 바꾸어 생각해볼 수 있다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, T, Q = map(int, input().split())
tree = [1 for _ in range(4*N)]
lazy = [-1]*(4*N)

def propagate(start, end, idx) :
  if lazy[idx] == -1 :
    return
  if start < end :
    lazy[idx*2] = lazy[idx]
    lazy[idx*2+1] = lazy[idx]
  tree[idx] = 1 << lazy[idx]
  lazy[idx] = -1

def update(start, end, idx, left, right, val) :
  propagate(start, end, idx)
  if left > end or right < start :
    return
  if left <= start <= end <= right :
    lazy[idx] = val
    propagate(start, end, idx)
    return
  mid = (start + end) // 2
  update(start, mid, idx*2, left, right, val)
  update(mid+1, end, idx*2+1, left, right, val)
  tree[idx] = tree[idx*2] | tree[idx*2+1]

def query(start, end, idx, left, right) :
  propagate(start, end, idx)
  if left > end or right < start :
    return 0
  if left <= start <= end <= right :
    return tree[idx]
  mid = (start + end) // 2
  lres = query(start, mid, idx*2, left, right)
  rres = query(mid+1, end, idx*2+1, left, right)
  return lres | rres

for _ in range(Q) :
  q, *cmd = input().split()
  if q == 'C' :
    x, y, z = map(int, cmd)
    if x > y :
      x, y = y, x
    update(0, N-1, 1, x-1, y-1, z-1)
  else :
    x, y = map(int, cmd)
    if x > y :
      x, y = y, x
    print(bin(query(0, N-1, 1, x-1, y-1)).count('1'))

풀이 완료!