[12844] XOR

https://www.acmicpc.net/problem/12844

lazy를 이용한 세그먼트 트리로 문제를 해결했습니다.-

XOR은 같은 값을 여러번하는 것은 의미없습니다.

한번하거나 안하거나와 같습니다.

홀수번 = 한번

짝수번 = 아예 안한 것

과 같기 떄문에 이 점을 이용해서 문제를 해결했습니다.

나머지 부분은 부분합 구하는 세그먼트 트리와 유사합니다.

코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <cmath>
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[500000];
 
int init(vi &tree, int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
    
    int mid = (start + end) / 2;
    return tree[node] = init(tree, node * 2, start, mid) ^ init(tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vi &tree, vi &lazy, int node, int start, int end) { 
    if (lazy[node] != 0) {
        tree[node] ^= lazy[node] * ((end - start + 1) % 2);
 
        if (start != end) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
 
int update_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right, int value) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return tree[node];
    else if (left <= start && end <= right) {
        tree[node] ^= value * ((end - start + 1) % 2);
 
        if (start != end) {
            lazy[node * 2] ^= value;
            lazy[node * 2 + 1] ^= value;
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right, value) ^ update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, value);
}
 
int xor_range(vi &tree, vi &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return 0;
    else if (left <= start && end <= right) return tree[node];
    
    int mid = (start + end) / 2;
    return xor_range(tree, lazy, 2 * node, start, mid, left, right) ^ xor_range(tree, lazy, 2 * node + 1, mid + 1, end, left, right);
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int height = ceil(log2(n));
    vi tree(1 << (int)(height + 1));
    vi lazy(1 << (int)(height  + 1));
 
    init(tree, 1, 0, n - 1);
 
    int m; 
    cin >> m;
    
    for (int i = 0; i < m; i++) {
        int cmd;
        int a, b, c;
        cin >> cmd;
 
        if (cmd == 1) {
            cin >> a >> b >> c;
            if (a > b) swap(a, b);
            update_range(tree, lazy, 1, 0, n - 1, a, b, c);
        }
        else {
            cin >> a >> b;
            if (a > b) swap(a, b);
            cout << xor_range(tree, lazy, 1, 0, n - 1, a, b)<< '\n';    
        }
    }
 
 
    return 0;
}