XOR (BOJ 14245)

문제

이미지 클릭

문제 설명

길이가 n인 배열이 0~n-1이 주어진다.
이후에 m개의 쿼리가 주어진다. 각 줄의 처음에는 t가 주어진다.
-t가 1인 경우에는 a,b,c를 입력 받음 => [a,b]의 배열 구간에 대해 c에 대해서 xor연산을 수행한다.
-t가 2인 경우에는 a를 입력 받음 => a번째 값을 출력해준다.

문제 해설

• xor연산

c++에서 xor연산은 ^ 연산자를 활용하면 가능하다.

• segment tree(laxy_propagation)

기본적으로 update, query, propagation을 활용하였다.

update
-세그먼트 트리에서 특정 구간 [x,y]에 대해서 XOR 값을 적용함.
-작동원리는 일반적인 세그먼트 트리와 비슷하지만 XOR연산을 해준다는 것 뻬고는 동일함.

query
-특정 위치 x에 대한 값을 반환해줌
-Lazy Propagation이 필요한 경우, propagation을 호출해 먼저 대기 중인 작업을 처리해줌.
-세그먼트 트리와 비슷한 로직으로 값을 return해줌.

propagation
-Lazy Propagation 기법을 사용하여, 현재 노드에 대기 중인 XOR 연산을 트리에 반영해줌.
-해당 노드가 관리하는 구간에 대한 XOR 연산을 지연시키는 대신, 실제로 필요할 때 한꺼번에 반영해줌.

최종 코드

#include<bits/stdc++.h>
#define INF 500004
using namespace std;
int n, m;
long long d[INF], t[INF * 4], lazy[INF * 4];

void propagation(int node, int l, int r) { //lazy_propagation
    if (lazy[node]) {
        t[node] ^= lazy[node] * (r - l + 1);
        if (l != r) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        lazy[node] = 0;
    }
}

void update(int node, int l, int r, int x, int y, long long val) { //구간 업데이트
    propagation(node, l, r);
    if (x > r || y < l) return;
    if (x <= l && r <= y) {
        lazy[node] ^= val;
        propagation(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, x, y, val);
    update(node * 2 + 1, mid + 1, r, x, y, val);
    t[node] = t[node * 2] ^ t[node * 2 + 1];
}

long long query(int node, int l, int r, int x) { //퀴리 값 리턴
    propagation(node, l, r);
    if (x < l || x > r) return 0;
    if (l == r) return t[node];
    int mid = (l + r) / 2;
    if (x <= mid) return query(node * 2, l, mid, x);
    else return query(node * 2 + 1, mid + 1, r, x);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> d[i];
    for (int i = 0; i < n; i++) update(1, 0, n - 1, i, i, d[i]);
    cin >> m;
    while (m--) {
        int t; cin >> t;
        if (t == 1) {
            int a, b, c;
            cin >> a >> b >> c;
            update(1, 0, n - 1, a, b, c);
        } else {
            int a;
            cin >> a;
            cout << query(1, 0, n - 1, a) << '\n';
        }
    }
}

이미지클릭