BOJ 12844 XOR, BOJ 14245 XOR, BOJ 11962 Counting Haybales (느리게 갱신되는 세그먼트 트리)

백준 BOJ 12844번 : XOR

12844번: XOR

문제 난이도 : Platinum III

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

 

 

 

느리게 갱신되는 세그먼트 트리 문제답게 역시 구간 업데이트 + 구간 대푯값 구하기 쿼리 문제입니다.

1번 쿼리에 대해서는 특정 구간의 모든 원소들에 대해 어떤 값을 XOR 하여 업데이트 해주어야 합니다.

2번 쿼리에 대해서는 특정 구간의 모든 원소들을 XOR 연산한 값을 출력해주어야 합니다.

 

 

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

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

int init(int n, int b, int e) {
    if(b == e) return u[n] = v[b];

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

    return u[n] = lv ^ rv;
}

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

    if((e - b + 1) % 2 == 1) u[n] ^= w[n];

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

    w[n] = 0;
}

void f(int n, int b, int e, int l, int r, int val) {
    lazy(n, b, e);

    if(r < b || e < l) return;

    if(l <= b && e <= r) {
        w[n] = val;

        lazy(n, b, e);

        return;
    }

    f(n*2, b, (b+e)/2, l, r, val);
    f(n*2 + 1, (b+e)/2 + 1, e, l, r, val);

    u[n] = u[n*2] ^ u[n*2 + 1];
}

int g(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 = g(n*2, b, (b+e)/2, l, r);
    int rv = g(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; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i];

    u.resize(N*4);
    init(1, 0, N-1);

    w.resize(N*4);

    int M; cin >> M;

    while(M--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int l, r, val; cin >> l >> r >> val;
            f(1, 0, N-1, l, r, val);
        }
        else if(Q == 2) {
            int l, r; cin >> l >> r;
            cout << g(1, 0, N-1, l, r) << "\n";
        }
    }
}

 

백준 BOJ 1395번 문제 '스위치'와 비슷한 아이디어를 사용하여 풀 수 있습니다. (링크 O)

 

세그먼트 트리에서 특정 구간을 담당하는 노드에 1번 쿼리를 수행할 때, 해당 노드에는 XOR 연산이 하위 노드들의 수만큼 수행되어야 합니다. (왜냐하면 하위 모든 리프 노드에 해당하는 수들에 대해 '각각' XOR 연산을 수행해야 하기 때문)

 

따라서 해당 노드에서 XOR 연산은 구간의 길이만큼 중첩되어 수행되어야 하는데, XOR 연산은 같은 수를 짝수 번 수행하면 원래의 수와 같으므로, 하위 노드의 구간의 길이인 e - b + 1이 홀수인 경우에만 XOR 연산을 한 번 수행해주면 됩니다.

 

나머지나 2번 쿼리 등은 일반적인 Lazy Propagation 문제와 형태가 동일하며, 연산의 종류만 XOR로 바꿔서 코드를 작성해주면 됩니다.

함수를 void 형식으로 작성할 것인지 int 형식으로 작성할 것인지는 정의하기 편한대로 하시면 될 것 같습니다.

 

 

 

 

백준 BOJ 14245번 : XOR

14245번: XOR

문제 난이도 : Platinum IV

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

 

 

 

위의 문제보다 간단한 문제입니다. (기존 문제인 12844번에서 조건 명시가 명확하지 않아 새로 등록된 문제인 것으로 보입니다.)

1번 쿼리는 동일하며, 2번 쿼리는 특정 구간에 대한 연산이 아닌 하나의 주소에 해당하는 원소만 출력해주면 됩니다.

따라서 12844번 문제의 풀이 코드에서 2번 쿼리 부분만 수정해주면 됩니다.

 

 

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

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

int init(int n, int b, int e) {
    if(b == e) return u[n] = v[b];

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

    return u[n] = lv ^ rv;
}

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

    if((e - b + 1) % 2 == 1) u[n] ^= w[n];

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

    w[n] = 0;
}

void f(int n, int b, int e, int l, int r, int val) {
    lazy(n, b, e);

    if(r < b || e < l) return;

    if(l <= b && e <= r) {
        w[n] = val;
        lazy(n, b, e);
        return;
    }

    f(n*2, b, (b+e)/2, l, r, val);
    f(n*2 + 1, (b+e)/2 + 1, e, l, r, val);

    u[n] = u[n*2] ^ u[n*2 + 1];
}

int g(int n, int b, int e, int idx) {
    lazy(n, b, e);

    if(b == e) return u[n];

    if(idx <= (b+e)/2) return g(n*2, b, (b+e)/2, idx);
    else return g(n*2 + 1, (b+e)/2 + 1, e, idx);
}

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

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i];

    u.resize(N*4);
    init(1, 0, N-1);

    w.resize(N*4);

    int M; cin >> M;

    while(M--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int l, r, val; cin >> l >> r >> val;
            f(1, 0, N-1, l, r, val);
        }
        else if(Q == 2) {
            int idx; cin >> idx;
            cout << g(1, 0, N-1, idx) << "\n";
        }
    }
}

 

위의 코드에서 함수 g의 형태만 바뀐 것을 확인할 수 있습니다.

b ~ e 구간을 반으로 나눠 idx가 왼쪽에 해당한다면 왼쪽 자식 노드로, 오른쪽에 해당한다면 오른쪽 자식 노드로 이동하는 과정을 반복하여 리프 노드에 도달하면 해당 노드의 값을 출력해주면 됩니다.

 

 

 

 

백준 BOJ 11962번 : Counting Haybales

11962번: Counting Haybales

문제 난이도 : Platinum IV

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

 

 

 

3가지 쿼리를 수행해야하는 문제입니다.

쿼리 M에 대해서는 구간의 최솟값을 출력해야 하고, 쿼리 P에 대해서는 구간의 모든 원소에 더하기 연산을 수행해주어야 하며, 쿼리 S에 대해서는 구간합을 출력해야 합니다.

 

일단 세그먼트 트리의 기본 문제들을 풀어보았다면, 이 문제는 단순히 최솟값을 저장하는 세그먼트 트리와 구간합을 저장하는 세그먼트 트리 2개를 구현하면 된다는 것을 알 수 있습니다.

 

그렇다면 여기에 lazy propagation을 따로 구현해야 할까요?

정답은 'propagation을 동시에 해주어야 한다'입니다.

왜냐하면 lazy propagation을 수행하는 함수를 한 번 수행해주면 propagation 값을 0으로 초기화해주기 때문에, 한 번 전파할 때 2개의 트리 모두에 전파 값을 반영시켜주어야 합니다.

 

 

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

vector<int> v, u1, u2, w; // v : array, u1 : min tree, u2 : sum tree, w : lazy

int init1(int n, int b, int e) {
    if(b == e) return u1[n] = v[b];

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

    return u1[n] = min(lv, rv);
}

int init2(int n, int b, int e) {
    if(b == e) return u2[n] = v[b];

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

    return u2[n] = lv + rv;
}

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

    u1[n] += w[n];
    u2[n] += (e-b+1)*w[n];

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

    w[n] = 0;
}

void f(int n, int b, int e, int l, int r, int add) {
    lazy(n, b, e);

    if(r < b || e < l) return;

    if(l <= b && e <= r) {
        if(b != e) {
            w[n*2] += add;
            w[n*2 + 1] += add;
        }
        u1[n] += add;
        u2[n] += (e-b+1)*add;
        return;
    }

    f(n*2, b, (b+e)/2, l, r, add);
    f(n*2 + 1, (b+e)/2 + 1, e, l, r, add);

    u1[n] = min(u1[n*2], u1[n*2 + 1]);
    u2[n] = u2[n*2] + u2[n*2 + 1];
}

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

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

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

    return min(lv, rv);
}

int h(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 u2[n];

    int lv = h(n*2, b, (b+e)/2, l, r);
    int rv = h(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;

    v.resize(N+1);
    for(int i=1; i<=N; i++) cin >> v[i];

    u1.resize(N*4);
    init1(1, 1, N);

    u2.resize(N*4);
    init2(1, 1, N);

    w.resize(N*4);

    while(M--) {
        char Q; cin >> Q;

        if(Q == 'M') {
            int l, r; cin >> l >> r;
            cout << g(1, 1, N, l, r) << "\n";
        }
        else if(Q == 'P') {
            int l, r, add; cin >> l >> r >> add;
            f(1, 1, N, l, r, add);
        }
        else if(Q == 'S') {
            int l, r; cin >> l >> r;
            cout << h(1, 1, N, l, r) << "\n";
        }
    }
}

 

풀이 코드는 위와 같습니다.

구현량이 많지만, 비슷한 원리의 세그먼트 트리 2개를 구현한다고 생각하면 크게 어렵지 않게 구현이 가능합니다.