백준1395 스위치

작성일 | In

문제 링크

  • http://icpc.me/1395

문제 출처

  • 2018 USACO November Gold 3

사용 알고리즘

  • Segment Tree

시간복잡도

  • O(m log n)

풀이

이 문제도 어제 올린 글과 같이 Lazy Propagation을 사용해 푸는 문제입니다.

문제를 처음 잡았을 때는 스위치의 상태를 반전시킨다는 의미에서 1을 xor해주는 방법도 생각을 했지만 다른 풀이가 생각나서 그 방법으로 구현을 했습니다.

[start, end]범위에서 켜져있는 스위치의 개수를 x라고 합시다.
[start, end]범위에 있는 모든 스위치의 상태를 반전시키면 켜져있는 스위치의 개수는 (end-start+1)-x개가 된다는 것은 자명합니다.
이것을 기반으로 구현했습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

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

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] = (end-start+1)-tree[node]; //관할 구역의 개수만큼 더함
		if(start != end){ //리프 노드가 아니면
			lazy[node*2] = !lazy[node*2];
			lazy[node*2+1] = !lazy[node*2+1];
		}
		lazy[node] = 0; //업데이트 완료
	}
}

int update_range(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 tree[node];
	}
	if(left<=start && end<=right){ //범위 포함
		tree[node] = (end-start+1)-tree[node];
		if(start!=end){
			lazy[node*2] = !lazy[node*2];
			lazy[node*2+1] = !lazy[node*2+1];
		}
		return tree[node];
	}
	int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}

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>>m;
	int tree_size = ceil(log2(n)) + 1;
    vll st(1 << tree_size);
    vll lazy(1 << tree_size);
    for (int i = 0; i < m; i++) {
    	int cmd, a, b;
        cin>>cmd>>a>>b;
        if (cmd) {
            cout << sum(st, lazy, 1, 1, n, a, b) << '\n';
        }
        else {
            update_range(st, lazy, 1, 1, n, a, b);
        }
    }
}