[백준/1395] 스위치 (Python)

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

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:08:22

 

---

 

문제 설명

 

 

준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.

준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.

하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다.

 

 

입력 및 출력

 

입력

 

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O가 0이면 Si번 스위치부터 Ti번 스위치까지 스위치 상태를 반전시키는 일이고 1이면 Si번 스위치부터 Ti번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

 

출력

 

입력에서 켜진 스위치 개수에 대한 답을 한 줄에 하나씩 출력한다.

 

입력 예시

 

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

 

출력 예시

 

1
2

 

 

---

 

풀이

 

Lazy segment tree 문제 특집. 이 문제 역시 범위 구간의 합과 업데이트를 요구하므로 둘 다 O(logN)이 소요되는 본 자료구조를 사용할 수 있겠다. 다만 다른 점이라면...

 

 

• self.lazy[idx] 는 모두 0 혹은 1의 값을 가진다.
• self.lazy[idx] 가 1이라면, 그 범위 내의 모든 전구가 반전됨을 의미한다. 즉 범위 내의 모든 전구 숫자는 end - start + 1개이고, 현재 켜진 숫자는 self.tree[idx]라면 반전될 때 총 end - start + 1 - self.tree[idx] 값으로 업데이트될 것이다.
• lazy propagation을 수행할 때, 자식 노드의 lazy가 0이라면 1, 1이라면 0으로 바꾸어 주어야 한다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

class LazySegTree() :
  def __init__(self) :
    self.tree = [0]*(4*N)
    self.lazy = [0]*(4*N)

  def propagate(self, start, end, idx) :
    if not self.lazy[idx] :
      return
    if start < end :
      self.lazy[idx*2] = 1 - self.lazy[idx*2]
      self.lazy[idx*2+1] = 1 - self.lazy[idx*2+1]
    self.tree[idx] = end - start + 1 - self.tree[idx]
    self.lazy[idx] = 0
  
  def update(self, left, right) :
    def _update(start, end, idx) :
      self.propagate(start, end, idx)
      if right < start or end < left :
        return
      if left <= start <= end <= right :
        self.lazy[idx] = 1 - self.lazy[idx]
        self.propagate(start, end, idx)
        return

      mid = (start + end) // 2
      _update(start, mid, idx*2)
      _update(mid+1, end, idx*2+1)
      self.tree[idx] = self.tree[idx*2] + self.tree[idx*2+1]
    _update(0, N-1, 1)

  def search(self, left, right) :
    def _search(start, end, idx) :
      self.propagate(start, end, idx)
      if right < start or end < left : 
        return 0
      if left <= start <= end <= right :
        return self.tree[idx]
      mid = (start + end) // 2
      return _search(start, mid, idx*2) + _search(mid+1, end, idx*2+1)
    print(_search(0, N-1, 1))

segtree = LazySegTree()
for _ in range(M) :
  q, a, b = map(int, input().split())
  if q == 0 :
    segtree.update(a-1, b-1)
  else :
    segtree.search(a-1, b-1)

풀이 완료!