BOJ 14245 XOR

22:17
구간 변경을 요구하므로 느리게 갱신되는 세그먼트 트리(lazy segment)를 이용하면 풀린다.

주의할 점) lazy 값을 자식들한테 넘겨줄 때 자식들이 있는지 없는지 부터 확인해야 함 -> out-of-bounds 됨.

#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] := v[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 update_lazy(int node, int start, int end) {
        if(tree[node].lazy == 0) return tree[node].value;
        tree[node].value ^= ((end-start+1)%2) * 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;
        return tree[node].value;
    }
    ll update(int node, int start, int end, int left, int right, ll diff) {
        update_lazy(node, start, end);
        if(right < start || end < left) return tree[node].value;
        if(left <= start && end <= right) {
            tree[node].lazy = diff;
            return update_lazy(node, start, end);
        }
        return tree[node].value = update(node * 2, start, (start + end) / 2, left, right, diff) ^ update(node * 2 + 1, (start + end) / 2 + 1, end, left, right, diff);
    }
    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);
    }
};

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 t; cin >> t;
        if(t==1) {
            int a,b,c; cin >> a >> b >> c;
            root.update(1,0,n-1,a,b,c);
        }
        else {
            int a; cin >> a;
            cout << root.XOR(1,0,n-1,a,a) << '\n';
        }
    }

    return 0;
}