스위치
https://www.acmicpc.net/problem/1395
1395번: 스위치
첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O
www.acmicpc.net
구간합 lazy propagation에서
조건을 심화한 문제이다.
1. 하나는 A번부터 B번 사이의 스위치 상태를 반전
-> 범위를 교체
lazy propagation
스위치 n개는 처음에는 다 꺼져있으므로
세그먼트 트리를 make 할 필요 없다.
tree.resize(tree_size)
하면 0으로 초기화 되니까!
세그먼트 트리에는
구간마다 켜져있는 스위치의 수를 저장.
구간이 합을 구하는 경우 lazy[node]에는
node 구간에 더할 숫자가 저장되어있었다.
이 문제는 lazy[node]에 node 구간의
스위치 반전 횟수를 저장한다.
스위치이므로
두 번 누르면 원상태로 된다.
즉, 홀수 번 누르는 것만 '유의미'하다.
update_lazy를 할 때
lazy[node] % 2 == 1인 경우에만
값 갱신을 해준다.
2. update_range() 함수
구간마다 켜져있는 스위치 수를
어떻게 저장할까?
(end - start + 1) -> 구간의 스위치 개수
tree[node] = (end - start + 1) - tree[node];
lazy 배열에는 스위치 반전 횟수를 저장 시키므로
if(start != end) {
lazy[node * 2] += 1;
lazy[node * 2 + 1] += 1;
}
+ cin, cout 처리 안해주면 시간 초과가 난다.
<소스 코드>
|
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> lazy;
vector<int> tree;
void update_lazy(int node, int start, int end)
{
// 스위치는 짝수번 돌리면
// 원 상태로 돌아옴
// 홀수만 유의미
if (lazy[node] % 2 == 1)
{
tree[node] = (end - start + 1) - tree[node];
// lazy propagation
if (start != end)
{
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
}
// 값이 필요 없다
// 스위치 바꾸는거니까
void update_range(int node, int start, int end, int left, int right)
{
update_lazy(node, start, end);
if (left > end || right < start)
return;
if (start >= left && end <= right)
{
tree[node] = (end - start + 1) - tree[node];
if (start != end)
{
lazy[node * 2] += 1;
lazy[node * 2 + 1] += 1;
}
return;
}
int mid = start + (end - start) / 2;
update_range(node * 2, start, mid, left, right);
update_range(node * 2 + 1, mid + 1, end, left, right);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(int node, int start, int end, int left, int right)
{
update_lazy(node, start, end);
if (left > end || right < start)
return 0;
if (start >= left && end <= right)
return tree[node];
int mid = start + (end - start) / 2;
int left_val = query(node * 2, start, mid, left, right);
int right_val = query(node * 2 + 1, mid + 1, end, left, right);
return left_val + right_val;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
int height = (int)ceil(log2(n));
int tree_size = (1 << (height + 1));
tree.resize(tree_size);
lazy.resize(tree_size);
// 처음엔 다 꺼져있으므로 make는 필요가 없다
// 다 0이 들어가 있을거니까!
int O, S, T;
while (q--)
{
cin >> O >> S >> T;
if (O == 0)
update_range(1, 0, n - 1, S - 1, T - 1);
else
cout << query(1, 0, n - 1, S - 1, T - 1) << '\n';
}
}
|
cs |