[BOJ] 백준 1395 스위치

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

 Input 

4 5

0 1 2

0 2 4

1 2 3

0 2 4

1 1 4

　 

 Output 

1

2

▶ 구간합을 가지는 세그먼트 트리 + Lazy Propagation을 이용

lazy[] = 반전시켜야 하는 횟수

          짝수인 경우는 반전시켜보아야 ON 상태의 스위치 개수에는 변화가 없기 때문에 홀수인 경우만 처리합니다.

         (if. 단말 노드의 ON/OFF 상태를 구해야하는 문제인 경우 변형 필요)

tree[]에서 스위치 ON 상태의 개수는 구간의 합 세그먼트 트리를 이용합니다.

(단말 노드에는 『0』 과 『1』 이 저장)

 

ex) 특정 노드(구간)의 단말 노드(leaf node) 개수 = e - s + 1 

→ 반전시 상태가 변하는 스위치 개수 = e - s + 1 - tree[node]

---

#include <stdio.h>
const int MAX_N = 1e5;
const int MAX_M = 1e5;
const int MAX_TREE_SIZE = 1 << 18;
int N, M; // 스위치개수, 명령개수
// 구간 합 Segment Tree
int tree[MAX_TREE_SIZE], lazy[MAX_TREE_SIZE];
 
void initTree(int n, int s, int e) {
    // 모든 스위치가 off 상태
    lazy[n] = tree[n] = 0;
    if (s == e)
        return;
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    initTree(L, s, m);
    initTree(R, m + 1, e);
}
 
void lazyPropagation(int node, int s, int e) {
    // 스위치의 개수가 반전되는 것이므로 홀수인 경우만 반전
    if (lazy[node] % 2) {
        tree[node] = e - s + 1 - tree[node];
 
        if (s != e) { 
            // 단말 노드가 아닌 경우 lazy 전파(자식 노드 존재)
            int L = node * 2, R = L + 1;
            lazy[L] += lazy[node];
            lazy[R] += lazy[node];
        }
    }
    // 전파하였으므로 현재 노드 lazy[] = 0
    lazy[node] = 0;
}
 
int query(int n, int s, int e, int qs, int qe) {
    lazyPropagation(n, s, e);
    // 범위를 벗어나는 경우
    if ((qe < s) || (e < qs))
        return 0;
    // Query 구간[qs, qe]이 [s, e]구간을 포함하는 경우
    if ((qs <= s) && (e <= qe))
        return tree[n];
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    // 구간합
    return query(L, s, m, qs, qe) + query(R, m + 1, e, qs, qe);
}
 
void update(int n, int s, int e, int qS, int qE) {
    int L = n * 2, R = L + 1, m = (s + e) / 2;
    lazyPropagation(n, s, e);
    if ((qE < s) || (e < qS))
        return;
    if ((qS <= s) && (e <= qE)) {
        tree[n] = e - s + 1 - tree[n];
        if (s != e) { 
            // 단말 노드가 아닌 경우
            // 양쪽 자식노드에게 반전 횟수 +1 전달
            lazy[L]++; lazy[R]++;
        }
        return;
    }
    update(L, s, m, qS, qE);
    update(R, m + 1, e, qS, qE);
    tree[n] = tree[L] + tree[R]; // 구간합
}
 
void solve() {
    int cmd, s, t;
    for (int i = 1; i <= M; i++) {
        scanf("%d %d %d", &cmd, &s, &t);
        if (cmd == 0)
            update(1, 1, N, s, t);
        else 
            printf("%d\n", query(1, 1, N, s, t));
    }
}
 
int main() {
    scanf("%d %d", &N, &M);
    initTree(1, 1, N);
    solve();
}