Lazy Propagation

코드

#include <stdio.h>
#include <algorithm>
#define SIZE (500500 << 2)

using namespace std;

int tre[SIZE], lazy[SIZE];

void propagate(int l, int r, int node) {
    if (lazy[node] != 0) {
        if (l < r) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        if ((r - l + 1) % 2)
            tre[node] ^= lazy[node];
        lazy[node] = 0;
    }
}

void update(int l, int r, int node, int pos, int val) {
    if (r < pos || pos < l)
        return;
    if (l == r) {
        tre[node] = val;
        return;
    }
    int mid = (l + r) / 2;
    update(l, mid, node * 2, pos, val);
    update(mid + 1, r, node * 2 + 1, pos, val);
    tre[node] = tre[node * 2] ^ tre[node * 2 + 1];
}

void update_xor(int l, int r, int node, int lo, int hi, int val) {
    propagate(l, r, node);
    if (r < lo || hi < l)
        return;
    if (lo <= l && r <= hi) {
        lazy[node] += val;
        propagate(l, r, node);
        return;
    }
    int mid = (l + r) / 2;
    update_xor(l, mid, node * 2, lo, hi, val);
    update_xor(mid + 1, r, node * 2 + 1, lo, hi, val);
    tre[node] = tre[node * 2] ^ tre[node * 2 + 1];
}

int get_xor(int l, int r, int node, int lo, int hi) {
    propagate(l, r, node);
    if (r < lo || hi < l)
        return 0;
    if (lo <= l && r <= hi)
        return tre[node];
    int mid = (l + r) / 2;
    return get_xor(l, mid, node * 2, lo, hi) ^ get_xor(mid + 1, r, node * 2 + 1, lo, hi);
}

int main()
{
    int n, i, a, m, b, c, t;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a);
        update(0, n - 1, 1, i, a);
    }
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d%d", &t, &a, &b);
        switch (t) {
            case 1:
                scanf("%d", &c);
                update_xor(0, n - 1, 1, min(a, b), max(a, b), c);
                break;
            case 2:
                printf("%d\n", get_xor(0, n - 1, 1, min(a, b), max(a, b)));
                break;
        }
    }
    return 0;
}

https://www.acmicpc.net/problem/12844 문제에 대한 풀이

정리

  • build : O(N)
  • update : O(logN)
    • 해당 노드에 lazy 값이 있다면, 값에 갱신을 해주는 작업을 먼저 한다
    • 세그먼트 트리와 거의 동일한 루틴이다. (포함관계일 때, lazy 값에 쓴다는점이 다르다)
  • query : O ((logN)^2)
    • 해당 노드에 lazy 값이 있다면, 값에 갱신을 해주는 작업을 먼저 한다
    • 세그먼트 트리와 동일한 루틴이다.
  • 실상은 lazy 를 전파하는 과정에서, 자식들이 변경됨을 보고 대표 값을 추정하는 과정이 한번 꼬여서 출제된다.

관련 문제

참고

results matching ""

    No results matching ""