백준 BOJ 1395번 : 스위치 (느리게 갱신되는 세그먼트 트리, Lazy Propagation)

백준 BOJ 1395번 : 스위치

문제 난이도 : Platinum III

알고리즘 분류 : 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree)

 

 

 

0번 쿼리에 대해서는 특정 구간의 모든 스위치를 toggle 해주고, 1번 쿼리에 대해서는 특정 구간의 스위치 중 켜져있는 스위치의 개수를 출력하는 문제입니다.

즉, 구간에 대한 업데이트와 구간에 대한 대푯값을 구하는 쿼리를 모두 수행하는 문제이므로 느리게 갱신되는 세그먼트 트리를 활용하여 문제를 풀이해야 합니다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> u, w; // u : tree, w : lazy

void lazy(int n, int b, int e) {
    if(w[n] % 2 == 0) return;

    u[n] = (e - b + 1) - u[n];

    if(b != e) {
        w[n*2] += w[n];
        w[n*2 + 1] += w[n];
    }

    w[n] = 0;
}

int upd(int n, int b, int  e, int l, int r) {
    lazy(n, b, e);

    if(r < b || e < l) return u[n];

    if(l <= b && e <= r) {
        u[n] = (e - b + 1) - u[n];

        if(b != e) w[n*2]++, w[n*2 + 1]++;

        return u[n];
    }

    int lv = upd(n*2, b, (b+e)/2, l, r);
    int rv = upd(n*2 + 1, (b+e)/2 + 1, e, l, r);

    return u[n] = lv + rv;
}

int query(int n, int b, int e, int l, int r) {
    lazy(n, b, e);

    if(r < b || e < l) return 0;
    if(l <= b && e <= r) return u[n];

    int lv = query(n*2, b, (b+e)/2, l, r);
    int rv = query(n*2 + 1, (b+e)/2 + 1, e, l, r);

    return lv + rv;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    u.resize(N*4);
    w.resize(N*4);

    while(M--) {
        int Q, a, b; cin >> Q >> a >> b;

        if(Q == 0) upd(1, 1, N, a, b);
        else if(Q == 1) cout << query(1, 1, N, a, b) << "\n";
    }
}

 

먼저 이 문제에서는 초기 스위치의 상태는 모두 0이므로 배열에 대한 값을 저장할 필요가 없습니다.

벡터 u는 세그먼트 트리로 활용하여 켜져있는 전구들의 개수의 구간 합을 나타내도록 하며, 벡터 w는 lazy propagation 값을 저장하는 트리라고 합시다.

 

lazy 함수가 호출되어 propagation을 수행할 때, 누적된 toggle의 횟수가 짝수 번이라면 전구의 상태는 그대로이므로 propagation을 수행할 필요가 없습니다. (2에 대한 나머지로 체크 가능)

누적 toggle 횟수가 홀수라면 전구의 상태가 바뀌어야 하므로 해당 노드가 담당하고 있는 구간의 켜져있는 전구 개수인 u[n] 값을 구간의 크기인 (e - b + 1)에서 기존 u[n]을 빼주는 방식으로 갱신해줄 수 있습니다. (전체에서 기존에 켜져있던 전구가 꺼지고 나머지 전구가 켜지므로)

이후 b != e 즉, 현재 n의 노드에 대해 자식 노드가 존재하는 경우 아래에 propagation 되는 값을 전파해줍니다.

 

0번 쿼리를 통해 구간의 전구 상태가 toggle 될 때는, 전파되지 않은 값이 남아있을 수 있으므로 lazy 함수를 먼저 한 번 실행해주고 그 다음 구간에 따른 처리를 해주면 됩니다.

구간 l ~ r이 구간 b~e 전체를 포함하는 경우 u[n] = (e - b + 1) - u[n]이라는 공식 역시 그대로 적용되며, 자식 노드가 있는 경우 toggle 횟수를 1씩 전파시킵니다.

나머지 경우는 구간을 쪼개면서 재귀적으로 함수를 작동시키면 됩니다.

upd 함수 자체는 기존의 세그먼트 트리의 작동 원리와 동일합니다.

 

query 함수 역시 기존의 세그먼트 트리의 구현과 동일하며, 세그먼트 트리(위 코드에서는 u 벡터)에서 구간의 합만 재귀적으로 구해오면 됩니다.