[ 백준 ] 14245번 - XOR (C++)

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

14245번: XOR

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/256

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

 

1. 초기 배열을 arr 배열에 저장합니다.

 

2. segmentTree의 리프 노드에 arr 배열의 값들을 넣습니다.

 

3. 느리게 갱신되는 세그먼트 트리를 이용하여 lazy 배열의 값들에 XOR한 값을 저장합니다.

 

4. 해당 쿼리를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int n, m;
int segTree[1050000];
int lazy[1050000];
int arr[500000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e)/2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] ^= lazy[node];
 
        if (s != e) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int a)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] ^= a;
        if (s != e) {
            lazy[node * 2] ^= a;
            lazy[node * 2 + 1] ^= a;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, a);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, a);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || e < idx) return;
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 0, n - 1);
 
    scanf("%d", &m);
 
    for (int i = 0; i < m; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
 
            updateTree(1, 0, n - 1, a, b, c);
        }
        else {
            int a;
            scanf("%d", &a);
 
            getTree(1, 0, n - 1, a);
        }
    }
}