백준12844 XOR

작성일 | In

문제 링크

  • http://icpc.me/12844

문제 출처

  • 2016 SCCC Summer Contest F번

사용 알고리즘

  • Segment Tree

시간복잡도

  • (m log n)

풀이

전에 올렸던 Lazy Propagation 설명에서 덧셈 연산을 xor연산으로 바꾼 뒤 적절히 연산을 하면 되는 문제입니다.

a xor b xor b의 결과는 a의 값과 같고, a xor 0의 결과도 a의 값과 같다는 것을 이용해 다음과 같은 사실을 알 수 있습니다.
어떤 수 b를 짝수 번 xor하면 0을 xor한 값과 같고, 홀수 번 xor하면 b를 한 번 xor한 값과 같다.
그러므로 update를 해줄 때, tree[node] ^= diff * ((end-start+1)%2); 와 같은 식으로 할 수 있습니다.
나머지 부분은 전에 올린 Lazy Propagation 설명과 같습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;

ll init(vll &arr, vll &tree, int node, int start, int end){
	if(start == end){
		return tree[node] = arr[start];
	}
	return tree[node] = init(arr, tree, node*2, start, (start+end)/2) ^ init(arr, tree, node*2+1, (start+end)/2+1, end);
}

void update_lazy(vll &tree, vll &lazy, int node, int start, int end){
	if(lazy[node] != 0){ //업데이트를 해야 할 경우
		tree[node] ^= lazy[node] * ((end-start+1)%2); //관할 구역의 개수만큼 더함
		if(start != end){ //리프 노드가 아니면
			lazy[node*2] ^= lazy[node];
			lazy[node*2+1] ^= lazy[node];
		}
		lazy[node] = 0; //업데이트 완료
	}
}

int update_range(vll &tree, vll &lazy, int node, int start, int end, int left, int right, ll diff){
	update_lazy(tree, lazy, node, start, end);
	if(left>end || right<start){ //범위 초과
		return tree[node];
	}
	if(left<=start && end<=right){ //범위 포함
		tree[node] ^= diff * ((end-start+1)%2);
		if(start!=end){
			lazy[node*2] ^= diff;
			lazy[node*2+1] ^= diff;
		}
		return tree[node];
	}
	return tree[node] = update_range(tree, lazy, node*2, start, (start+end)/2, left, right, diff) ^
    					update_range(tree, lazy, node*2+1, (start+end)/2+1, end, left, right, diff);
}

ll sum(vll &tree, vll &lazy, int node, int start, int end, int left, int right){
	update_lazy(tree, lazy, node, start, end);
	if(left>end || right<start) return 0;
	if(left<=start && end<=right) return tree[node];
	return sum(tree, lazy, node*2, start, (start+end)/2, left, right) ^ sum(tree, lazy, node*2+1, (start+end)/2+1, end, left, right);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin>>n;
	vll arr(n);
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	int h = (int)ceil(log2(n))+1;
	int size = (1 << h);
	vll tree(size);
	vll lazy(size);
	init(arr, tree, 1, 0, n-1);

	cin>>m;

	for(int i=0; i<m; i++){
		int t; cin>>t;
		if(t == 1){
			int b, c; ll d; cin>>b>>c>>d;
			if(b>c)swap(b, c);
			update_range(tree, lazy, 1, 0, n-1, b, c, d);
		}
		if(t == 2){
			int b, c; cin>>b>>c;
			if(b>c)swap(b, c);
			cout << sum(tree, lazy, 1, 0, n-1, b, c) << "\n";
		}
	}
}