BOJ 12844 XOR

느리게 갱신되는 세그먼트 트리를 이용하여 푼다.
느리게 갱신되는 세그먼트 트리를 사용할 때는 항상 lazy 값을 업데이트 시켜준 다음 뭔가를 할 수 있다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define x first
#define y second
#define all(v) (v).begin(), (v).end()

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

using pll = pair<ll, ll>;
#define value first
#define lazy second

class segment {
public:
    vector<pll> tree; //tree[node] := a[start ~ end] 의 합

    segment() {}
    segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size, pll(0,0));
    }
    ll init(vector<ll> &a, int node, int start, int end) {
        if(start == end) return tree[node].value = a[start];
        else return tree[node].value = init(a, 2 * node, start, (start + end) / 2) ^
                                 init(a, 2 * node + 1, (start + end) / 2 + 1, end);
    }
    ll XOR(int node, int start, int end, int left, int right) {
        update_lazy(node, start, end);
        if(right < start || end < left) return 0;
        if(left <= start && end <= right) return tree[node].value;
        return XOR(node * 2, start, (start + end) / 2, left, right) ^
               XOR(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
    void update(int node, int start, int end, int left, int right, ll diff) {
        update_lazy(node, start, end);
        if(right < start || end < left) return;
        if(left <= start && end <= right) {
            tree[node].lazy = diff;
            update_lazy(node, start, end);
            return;
        }
        update(node * 2, start, (start + end) / 2, left, right, diff);
        update(node * 2 + 1, (start + end) / 2 + 1, end, left, right, diff);
        tree[node].value = tree[2*node].value ^ tree[2*node+1].value;
    }
    void update_lazy(int node, int start, int end) {
        if((start-end+1)%2) tree[node].value ^= tree[node].lazy;
        if(start != end) {
            tree[2*node].lazy ^= tree[node].lazy;
            tree[2*node+1].lazy ^= tree[node].lazy;
        }
        tree[node].lazy = 0;
    }
};

int N, M;
vector<ll> v;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

    segment root(N);
    root.init(v, 1, 0, N-1);

    cin >> M;
    while(M--) {
        int q, i, j, k; cin >> q >> i >> j;
        if(q == 1) {
            cin >> k;
            root.update(1,0,N-1,i,j,k);
        }
        else cout << root.XOR(1,0,N-1,i,j) << '\n';
    }

    return 0;
}