[백준] 스위치

 

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

1395번: 스위치

 

1. 문제 이해

N개의 스위치가 주어지고 두가지 연산이 주어집니다. A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져있는 스위치의 개수를 세는 것입니다.

2. 문제 접근

레이지 프로퍼게이션을 활용한 세그멘트 트리를 활용하는 문제입니다. lazy배열에는 현재 범위에 있는 스위치들을 반전시키는 작업이 필요한지 여부를 가지고 있습니다. 범위 내에서 스위치를 반전시키는 횟수가 짝수번이면 굳이 스위치를 반전시킬 필요가 없기 때문입니다.

3. 풀이

import sys, heapq
from collections import deque

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

# n: 스위치의 개수, m: 일의 개수
n, m = tuple(map(int, input().split()))

# lazy[i]가 1이면 변경이 필요하고 0이면 필요하지 않다.
lazy = [0] * (4 * n)
tree = [0] * (4 * n)

def propagate(start, end, node):
    if lazy[node] != 0:
        # 범위를 키거나 끝다.
        tree[node] = (end - start + 1) - tree[node]
        if start != end:
            lazy[node * 2] ^= 1
            lazy[node * 2 + 1] ^= 1

        lazy[node] = 0

def range_sum(start, end, left, right, node):
    propagate(start, end, node)

    if start > right or end < left:
        return 0

    if left <= start and end <= right:
        return tree[node]

    mid = (start + end) // 2

    return range_sum(start, mid, left, right, node * 2) + range_sum(mid + 1, end, left, right, node * 2 + 1)

def range_update(start, end, left, right, node):
    propagate(start, end, node)

    # 범위에 포함되지 않은 경우
    if start > right or end < left:
        return

    # 범위에 포함된 경우
    if left <= start and end <= right:
        tree[node] = (end - start + 1) - tree[node]

        # lazy_propagation
        if start != end:
            lazy[node * 2] ^= 1
            lazy[node * 2 + 1] ^= 1

        return

    mid = (start + end) // 2

    range_update(start, mid, left, right, node * 2)
    range_update(mid + 1, end, left, right, node * 2 + 1)

    tree[node] = tree[node * 2] + tree[node * 2 + 1]

for _ in range(m):
    cmd, s, e = tuple(map(int, input().split()))
    # range_update
    if cmd == 0:
        range_update(0, n - 1, s - 1, e - 1, 1)
    # range_sum
    else:
        print(range_sum(0, n - 1, s - 1, e - 1, 1))

4. 회고

스위치를 반전시키는 과정에서 기존에 켜져있는 스위치만큼 꺼주었어야하는데 범위 전체를 키거나 끄는 것으로 생각했스빈다. 이 부분을 캐치하지 못해 정답 풀이를 보고 알게 되었습니다. 조금 더 신중하게 생각해야함을 알 수 있었습니다.