[C++] 백준 12844번: XOR

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

12844번: XOR

 

이 글은 Segment Tree의 Lazy Propagation을 배경으로 작성하였다.

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-2

[Python] Lazy Propagation (백준 10999번: 구간 합 구하기 2)

 

 > 접근

우선 XOR 연산은 교환법칙이 성립한다. 예를 들어 0111^1100^1011을 수행한다고 했을 때, (0111^1100)^1011과 0111^(1100^1011)의 결과가 같다. 이를 통해 세그먼트 트리를 이용할 수 있다는 것을 알 수가 있다. 방금 살펴본 예시를 다시 이용해보면, 세그먼트 트리는 다음과 같이 구성된다.

이러한 접근을 기반으로 세그먼트 트리를 구성한다. 하지만 이 상태로 제출하면 TLE가 날 것이다. 따라서 Lazy Propagation을 이용한다.

 

 > 풀이

먼저 Lazy Propagation을 위해 lazy에 저장할 값을 정의해야한다. 우선 위 예시에서 0~1 인덱스에 xor한다고 해보자. 이 때, 어떤 값을 xor하든지간에 1011이라는 값은 변함이 없는 것을 알 수 있다. 가령 0101을 xor한다고 했을 때, 해당 연산을 수학식으로 풀어보면 다음과 같다.

(0111 ^ 0101) ^ (1100 ^ 0101)

이것이 '상쇄'되는 이유는 교환법칙에 의해 다음과 같이 전개할 수 있기 때문이다.

(0111 ^ 1100) ^ (0101 ^ 0101) = (0111 ^ 1100) ^ 0000 = 0111 ^ 1100

즉, 0101이 짝수만큼 들어갔기 때문이다.

 

여기서 결론짓자면, xor 연산을 할 값을 lazy 저장한 뒤에, propagate를 할 때 대상 노드가 가리키는 노드의 개수가 홀수일 때만 트리값을 변경하면 된다. 예를 들어, 방금 든 예시에서는 1011이라는 노드가 0~1, 즉 짝수만큼의 노드를 가리키므로 트리를 수정하지 않고 lazy값만 전달하게 된다. 반대로 위 사진에서의 루트 노드인 0000은 0~2(개수가 홀수)를 가리키므로 xor 연산을 1번 해준 뒤 전파해준다.

 

마지막으로 lazy의 default 값은 0인데, 특정 값에 0을 xor해주면 값이 그대로 유지되기 때문이다.

 

#include <bits/stdc++.h>
using namespace std;

int A[500001];
int tree[500000 * 4 + 1];
int lazy[500000 * 4 + 1];

void initializeTree(int index, int start, int end) {
	if (start == end) {
		tree[index] = A[start];
		return;
	}

	int mid = (start + end) / 2;
	initializeTree(index * 2, start, mid);
	initializeTree(index * 2 + 1, mid + 1, end);

	tree[index] = tree[index * 2] ^ tree[index * 2 + 1];
}

void propagateTree(int index, int start, int end) {
	if (lazy[index] != 0) {
		if ((end - start + 1) % 2 == 1) {
			tree[index] ^= lazy[index];
		}

		if (start != end) {
			lazy[index * 2] ^= lazy[index];
			lazy[index * 2 + 1] ^= lazy[index];
		}

		lazy[index] = 0;
	}
}

void updateTree(int index, int start, int end, int val, int left, int right) {
	propagateTree(index, start, end);

	if (right < start || end < left) return;

	if (left <= start && end <= right) {
		lazy[index] ^= val;
		propagateTree(index, start, end);

		return;
	}

	int mid = (start + end) / 2;
	updateTree(index * 2, start, mid, val, left, right);
	updateTree(index * 2 + 1, mid + 1, end, val, left, right);

	tree[index] = tree[index * 2] ^ tree[index * 2 + 1];
}

int queryTree(int index, int start, int end, int left, int right) {
	propagateTree(index, start, end);

	if (right < start || end < left) return 0; // An exception

	if (left <= start && end <= right) {
		return tree[index];
	}

	int mid = (start + end) / 2;
	int res1 = queryTree(index * 2, start, mid, left, right);
	int res2 = queryTree(index * 2 + 1, mid + 1, end, left, right);

	return res1 ^ res2;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N;
	cin >> N;

	int i;
	for (i = 1; i < N + 1; i++) {
		cin >> A[i];
	}

	initializeTree(1, 1, N);

	int M;
	cin >> M;
	int op, a, b, c;
	for (i = 0; i < M; i++) {
		cin >> op;
		if (op == 1) {
			cin >> a >> b >> c;
			updateTree(1, 1, N, c, a + 1, b + 1);
		}
		else {
			cin >> a >> b;
			cout << queryTree(1, 1, N, a + 1, b + 1) << "\n";
		}
	}

	return 0;
}