백준 12844 c++ "XOR" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리를 이용해서 푸는 문제이다.

Update할 때 구간 전체를 업데이트 해야되므로 lazy전파를 이용해야 시간내에 풀 수 있다.

이 문제만의 특이점은 xor연산이라고 생각한다.

end-start+1 을 2로 나눴을 때 ==1 인 경우만 tree[node] 의 값을 update해줘야 된다.

이 부분만 잘 이해하고 있으면 문제를 풀 수 있게 된다.

[코드 해설]

1. 입력 처리 (Input 함수)

Input 함수는 세그먼트 트리 초기화를 위한 입력값을 처리합니다.

• N 입력: 세그먼트 트리의 배열 크기 N을 입력받습니다.
• arr 벡터 초기화: 배열 크기를 N+1로 설정하고 입력 값을 1번 인덱스부터 채웁니다. (1번부터 시작하는 인덱싱을 사용)
• tree와 lazy 초기화:
  • tree: 세그먼트 트리로 사용할 배열 크기를 4 * N으로 설정.
  • lazy: 지연(lazy) 배열도 같은 크기로 초기화하며, 초기값은 모두 0입니다.

---

2. 세그먼트 트리 초기화 (Init 함수)

Init 함수는 세그먼트 트리를 초기화합니다.

• 리프 노드 처리: start == end인 경우, tree[node]에 arr[start] 값을 저장합니다.
• 구간 합산: 중간 인덱스 mid를 기준으로 왼쪽, 오른쪽 자식 노드에서 값을 재귀적으로 계산하고, tree[node]에 저장합니다.
• XOR 연산 사용: 세그먼트 트리는 XOR 연산을 기준으로 동작합니다. 즉, 각 구간의 XOR 값을 저장합니다.

---

3. 지연 전파 (Propagation 함수)

Propagation 함수는 지연 업데이트(lazy propagation)를 처리합니다.

• 지연 값 확인: lazy[node]가 0이 아닌 경우에만 실행됩니다.
• XOR 값 계산: 현재 구간의 노드가 커버하는 길이가 홀수라면 tree[node]에 lazy[node] 값을 XOR합니다.
• 자식 노드 갱신: 자식 노드로 지연 값을 전달합니다.
• 지연 값 초기화: lazy[node] 값을 0으로 초기화하여 처리가 완료되었음을 표시합니다.

---

4. 구간 업데이트 (Update 함수)

Update 함수는 지정된 구간에 값을 업데이트합니다.

• 지연 전파: 노드에 저장된 지연 값을 먼저 적용하여 최신 상태로 만듭니다.
• 구간 확인:
  • 완전히 벗어난 구간은 처리하지 않습니다.
  • 업데이트 범위에 완전히 포함되는 경우, 노드에 XOR 값을 적용하고 자식 노드에 지연 값을 설정합니다.
• 재귀 호출: 범위가 걸쳐 있는 경우, 중간 인덱스를 기준으로 왼쪽과 오른쪽 자식 노드를 재귀적으로 호출하여 업데이트를 진행합니다.
• 부모 노드 갱신: 자식 노드에서 값을 받아 XOR 연산으로 부모 노드를 갱신합니다.

---

5. 구간 질의 (Query 함수)

Query 함수는 지정된 구간의 XOR 값을 반환합니다.

• 지연 전파: 노드에 저장된 지연 값을 먼저 적용합니다.
• 구간 확인:
  • 완전히 벗어난 구간은 0을 반환합니다.
  • 질의 범위에 완전히 포함되는 경우, 현재 노드 값을 반환합니다.
• 재귀 호출: 범위가 걸쳐 있는 경우, 중간 인덱스를 기준으로 왼쪽과 오른쪽 자식 노드에서 값을 받아 XOR 연산으로 결과를 반환합니다.

---

6. 질의 처리 (processQueries 함수)

사용자의 질의를 처리하는 함수입니다.

• 입력 형식: 질의 수 M을 입력받고, 각 질의에 따라 업데이트 또는 구간 질의를 처리합니다.
  • operation == 1인 경우, 지정된 구간에 값을 XOR하여 업데이트를 수행합니다.
  • operation == 2인 경우, 지정된 구간의 XOR 값을 계산하여 출력합니다.

[소스 코드]

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

int arraySize, queryCount;
int inputArray[500001];
int segmentTree[500001 * 4];
int lazyPropagation[500001 * 4];

void buildTree(int start, int end, int node) {
    if (start == end) {
        segmentTree[node] = inputArray[start];
        return;
    }
    int mid = (start + end) / 2;
    buildTree(start, mid, node * 2);
    buildTree(mid + 1, end, node * 2 + 1);
    segmentTree[node] = (segmentTree[node * 2] ^ segmentTree[node * 2 + 1]);
}

void applyLazy(int node, int left, int right) {
    if (lazyPropagation[node]) {
        if ((right - left + 1) % 2 == 1) segmentTree[node] ^= lazyPropagation[node];
        if (left != right) {
            lazyPropagation[node * 2] ^= lazyPropagation[node];
            lazyPropagation[node * 2 + 1] ^= lazyPropagation[node];
        }
        lazyPropagation[node] = 0;
    }
}

long long queryXor(int node, int start, int end, int left, int right) {
    applyLazy(node, start, end);
    if (left > end || right < start) return 0;
    if (left <= start && end <= right) return segmentTree[node];
    int mid = (start + end) / 2;
    long long leftXor = queryXor(node * 2, start, mid, left, right);
    long long rightXor = queryXor(node * 2 + 1, mid + 1, end, left, right);
    return (leftXor ^ rightXor);
}

void updateTree(int node, int start, int end, int left, int right, int value) {
    applyLazy(node, start, end);
    if (start > right || end < left) return;
    if (left <= start && end <= right) {
        if ((end - start + 1) % 2 == 1) segmentTree[node] ^= value;
        if (start != end) {
            lazyPropagation[node * 2] ^= value;
            lazyPropagation[node * 2 + 1] ^= value;
        }
        return;
    }
    int mid = (start + end) / 2;
    updateTree(node * 2, start, mid, left, right, value);
    updateTree(node * 2 + 1, mid + 1, end, left, right, value);
    segmentTree[node] = (segmentTree[node * 2] ^ segmentTree[node * 2 + 1]);
}

void processQueries() {
    buildTree(0, arraySize - 1, 1);
    cin >> queryCount;
    for (int i = 1; i <= queryCount; i++) {
        int operation, left, right, value;
        scanf("%d", &operation);
        if (operation == 1) {
            scanf("%d %d %d", &left, &right, &value);
            updateTree(1, 0, arraySize - 1, left, right, value);
        } else {
            scanf("%d %d", &left, &right);
            cout << queryXor(1, 0, arraySize - 1, left, right) << "\n";
        }
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> arraySize;
    for (int i = 0; i < arraySize; i++) scanf("%d", &inputArray[i]);
    processQueries();
    return 0;
}