백준 12844 - XOR(C++)

문제 링크입니다. https://www.acmicpc.net/problem/12844

 

 

해당 문제를 풀기 위해선 XOR의 기본적인 특징을 하나 알아야합니다.

 

예를 들어, 10011 ^ 11100을 한다면 01111이 나옵니다. 

이때, 11100을 다시 XOR을 한다면 01111 ^ 11100 = 10011이 됨으로 다시 원래대로 돌아옴을 알 수 있습니다.

->  "같은 수를 짝수번 XOR 한다면, 원상태로 돌아온다"가 됩니다.

 

그러므로, 구간의 값을 가진 트리에 XOR을 한다면 구간의 길이를 통해서 XOR 여부를 확인해주면 됩니다.

 

쿼리의 개수가 크니, 느리게 갱신되는 세그먼트 트리를 사용하고, 

이때 사용되는 lazy 배열에 해줘야하는 XOR 값을 계속 XOR 해주면, 0 또는 XOR 값으로만 남아 있을 것입니다.

 

이를 통해, XOR의 여부도 확인이 가능합니다.

 

 

자세한 것은 코드를 참고해주세요.

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

using namespace std;

int N, M;
int Index[500001];
int Tree[500001 * 4];
int lazy[500001 * 4];

void segment_tree(int st, int fin, int node) {
    if (st == fin) {
        Tree[node] = Index[st];
        return;
    }
    int mid = (st + fin) / 2;
    segment_tree(st, mid, node * 2);
    segment_tree(mid + 1, fin, node * 2 + 1);
    Tree[node] = (Tree[node * 2] ^ Tree[node * 2 + 1]);
}

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

long long return_xor(int node, int st, int fin, int left, int right) {
    update_lazy(node, st, fin);
    if (left > fin || right < st) return 0;
    if (left <= st && fin <= right) return Tree[node];
    int mid = (st + fin) / 2;
    long long left_xor = return_xor(node * 2, st, mid, left, right);
    long long right_xor = return_xor(node * 2 + 1, mid + 1, fin, left, right);
    return (left_xor ^ right_xor);
}

void change_tree(int node, int st, int fin, int left, int right, int Xor) {
    update_lazy(node, st, fin);
    if (st > right || fin < left) return;
    if (left <= st && fin <= right) {
        if((fin - st + 1) % 2 == 1) Tree[node] = Tree[node] ^ Xor;
        if (st != fin) {
            lazy[node * 2] ^= Xor;
            lazy[node * 2 + 1] ^= Xor;
        }
        return;
    }
    int mid = (st + fin) / 2;
    change_tree(node * 2, st, mid, left, right, Xor);
    change_tree(node * 2 + 1, mid + 1, fin, left, right, Xor);
    Tree[node] = (Tree[node * 2] ^ Tree[node * 2 + 1]);
}

void solve() {
    segment_tree(0, N - 1, 1);
    cin >> M;
    for (int i = 1; i <= M; i++) {
        int a, x, y, Xor;
        scanf("%d", &a);
        if (a == 1) { // x~y에 z를 xor한다.
            scanf("%d %d %d", &x, &y, &Xor);
            change_tree(1, 0, N - 1, x, y, Xor);  
        }
        else { // x~y까지 xor값을 구한다.
            scanf("%d %d", &x, &y);
            cout << return_xor(1, 0, N - 1, x, y) << "\n";
        }
    }
}

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

 

 

질문 및 조언은 댓글을 남겨주세요.