[백준 12844번] [Lazy propagation] XOR

Approach

문제를 보자마자 구간에 대한 정보를 계속해서 업데이트 하는 상황이므로 Lazy propagation 문제임은 직관적으로 잘 파악했을 것이다.

 

하지만, 기본적인 합 세그와 달리 XOR 연산을 처리하는 세그이므로 XOR 연산의 성질을 잘 생각해볼 필요가 있다.

• a XOR 0 = a
• b XOR b = 0
• a XOR b XOR c = (a XOR b) XOR c = a XOR (b XOR c) : associative

위 성질을 이용하면, 구간 [a, b]에 c를 xor연산을 하게 되면 seg[node] XOR (c * ((b - a + 1) % 2)))와 같다는 것을 쉽게 파악할 수 있다. 왜냐하면 c를 짝수면 XOR처리를 하게 되면 결과적으로 0과 XOR 연산을 하는 것과 같아지고, 홀수면 단순히 c와 XOR 연산을 하는 것과 같기 때문이다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};

ll seg[2000000];
ll lazy[2000000];

void init(int node, int start, int end, int index, ll value){
    if(index < start || end < index) return;
    seg[node] ^= value;
    if(start == end){
        return;
    }
    int mid = (start + end) >> 1;
    init(node * 2, start, mid, index, value);
    init(node * 2 + 1, mid + 1, end, index, value);
}

void propagate(int node, int start, int end){
    if(lazy[node]){
        if(start != end){
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        seg[node] ^= lazy[node] * ((end - start + 1) % 2);
        lazy[node] = 0;
    }
}

void update(int node, int start, int end, int left, int right, ll value){
    propagate(node, start, end);
    if(right < start || end < left) return;
    if(left <= start && end <= right){
        lazy[node] ^= value;
        propagate(node, start, end);
        return;
    }
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, left, right, value);
    update(node * 2 + 1, mid + 1, end, left, right, value);
    seg[node] = seg[node * 2] ^ seg[node * 2 + 1];
}

ll query(int node, int start, int end, int left, int right){
    propagate(node, start, end);
    if(right < start || end < left) return 0;
    if(left <= start && end <= right) return seg[node];
    int mid = (start + end) >> 1;
    return query(node * 2, start, mid, left, right) ^ query(node * 2 + 1, mid + 1, end, left, right);
}

int main() {
    fastio;
    memset(seg, 0, sizeof(seg));
    memset(lazy, 0, sizeof(lazy));
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        init(1, 0, 500000, i, t);
    }

    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int a, b, c, d;
        cin >> a;
        if(a == 1){
            cin >> b >> c >> d;
            update(1, 0, 500000, b, c, d);
        }
        else{
            cin >> b >> c;
            cout << query(1, 0, 500000, b, c) << "\n";
        }
    }
    return 0;
}