[백준] 1395번 스위치

1395 스위치

문제

---

준규네 집에는 총 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번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

출력

---

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

---

풀이)

segment tree + lazy propagate 를 이용해서 푼 문제다.

스위치가 100,000개 이므로, 계산하기 쉽게 넉넉히 4 * 100,000을 트리크기로 정해줬다.

스위치가 켜진값을 1, 꺼진 값은 0 이라고 하고 반전시키는 계산은 1과 XOR시켜줬다.

(1 XOR 1 = 0,     0 XOR 1 = 1)

구간에 갱신이 일어난 후

propagate함수에서 tree에 적용시켜줄 때

                                                                                                                          

구간 범위에서 켜져있는 스위치 초기 개수가 n개일때, 반전시키면 켜져있는 스위치는 (구간 범위 - n)개임을 알아두자.

[Left, Right]                                                                                          (Right - Left + 1 - n)

(예시)

범위가 2일때, 켜져있는 합이 0이면 -> 켜져야하는 스위치는  2 - 0 = 2 

                               합이 1이면 -> 2 - 1 = 1

                               합이 2이면 -> 2 - 2 = 0

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, m;
int tree[400000];//켜져있는 스위치 합 저장
int lazy[400000];//lazy의 값이 1이면 -> 반전시켜야한다.
 
void propagate(int node,int nodeL,int nodeR) {
    //nodeL부터 nodeR까지를 반전시킨다?
    //범위가 2일때, 켜져있는 합이 0이면 -> 켜져야 하는 스위치 2, 합이 1이면-> 1, 합이 2이면 0
    tree[node] = (nodeR - nodeL + 1) - tree[node];
    if (nodeL != nodeR) {
        lazy[node * 2] ^= 1;
        lazy[node * 2 + 1] ^= 1;
    }
    lazy[node] = 0;
}
 
void update(int L,int R,int node,int nodeL,int nodeR) {
    if (lazy[node] != 0) propagate(node, nodeL, nodeR); // propagate먼저
    if (nodeR < L || R < nodeL)return;
    if (L <= nodeL && nodeR <= R) {//범위안에 든다면, 스위치 반전
        lazy[node] ^= 1;
        propagate(node, nodeL, nodeR);
        return;
    }
    int mid = (nodeL + nodeR) / 2;
    //자식들 업데이트
    update(L, R, node * 2, nodeL, mid);
    update(L, R, node * 2 + 1, mid+1, nodeR);
    //본인 새로 업데이트
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
int query(int L,int R,int node,int nodeL,int nodeR) { //스위치 켜진 합
    if (lazy[node] != 0) propagate(node, nodeL, nodeR); // propagate먼저
    if (nodeR < L || R < nodeL)return 0;
    if (L <= nodeL && nodeR <= R) return tree[node];
    int mid = (nodeL + nodeR) / 2;
    return query(L, R, node * 2, nodeL, mid) + query(L, R, node*2+1, mid + 1, nodeR);
}
 
 
int main() {
    scanf("%d %d", &n, &m);
 
    while (m--)
    {
        int o, s, t;
        scanf("%d %d %d", &o, &s, &t);
        if (s > t)swap(s, t);
        if (o == 0) {
            update(s, t, 1, 1, n);
        }
        else {
            printf("%d\n", query(s, t, 1, 1, n));
        }
 
    }
    return 0;
}

결과)