[1395] 스위치

문제 링크 : https://www.acmicpc.net/problem/1395

1395 - 스위치

본문

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

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

쿼리가 전부 특정 구간에서의 연산을 하도록 되어 있으니 세그먼트 트리, $N \times M$의 크기가 매우 크므로 lazy propagation이 필요하다는 것을 빠르게 알 수 있다.

이 문제는 세그먼트 트리 문제들 중 그나마 일반형이라고 생각되는 문제이다. 구간의 합이나 곱 같은 것을 저장하는 것은 아니지만 구간에서 스위치가 켜진 것의 개수를 기록하면 된다. 즉 계산 식을 덧셈이 아니라 반전식을 넣으면 된다. 그리고 lazy 또한 특정 값이 아니라 on/off만 기록하면 된다.

나머지는 일반적인 세그먼트 트리와 똑같이 동작한다. 사실상 일반형이라고 얘기할 수 있을 문제.

• 참고 알고리즘 : 느리게 갱신되는 세그먼트 트리

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 23

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 100000
int segtree[MAX_IDX * 4];
bool lazy[MAX_IDX * 4];
int n;

void update_lazy(int node, int s, int e) {
    if (lazy[node] == true) {
        segtree[node] = (e - s + 1) - segtree[node];
        if (s < e) {
            lazy[node * 2] ^= true;
            lazy[node * 2 + 1] ^= true;
        }

        lazy[node] = false;
    }
    return;
}
void update_range(int node, int s, int e, int l, int r) {
    update_lazy(node, s, e);

    if (l > e || r < s) {
        return;
    } else if (l <= s && e <= r) {
        segtree[node] = (e - s + 1) - segtree[node];
        if (s < e) {
            lazy[node * 2] ^= true;
            lazy[node * 2 + 1] ^= true;
        }
        return;
    }

    update_range(node * 2, s, (s + e) / 2, l, r);
    update_range(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
    segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    return;
}

int query(int node, int s, int e, int l, int r) {
    update_lazy(node, s, e);
    if (l > e || r < s) {
        return 0;
    } else if (l <= s && e <= r) {
        return segtree[node];
    }

    return query(node * 2, s, (s + e) / 2, l, r) + query(node * 2 + 1, (s + e) / 2 + 1, e, l, r);
}

int main() {
    int m;
    scanf("%d %d", &n, &m);

    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        switch (a) {
            case 0: {
                update_range(1, 0, n - 1, b - 1, c - 1);
                break;
            }
            case 1: {
                printf("%d\n", query(1, 0, n - 1, b - 1, c - 1));
            }
        }
    }

    return 0;
}