https://www.acmicpc.net/problem/8330
수열이 a1, a2, ..., an 으로 주어졌을때 1 ~ ai 범위의 숫자를 적절하게 골라서 1 ~ N의 수가 하나씩 등장하도록 만들어야 합니다.
5
3 4 3 2 5즉 이런 수열이 주어졌을 때
a1은 1 ~ 3 중에서 2
a2는 1 ~ 4 중에서 4
a3은 1 ~ 3 중에서 3
a4는 1 ~ 2 중에서 1
a5는 1 ~ 5 중에서 5
이렇게 골라서 1 ~ N까지 하나씩 등장하도록 순열을 만들 수 있습니다.
그리고 수열을 M번 수정하여 각각 수정된 수열에서도 위처럼 1 ~ N을 만들 수 있는지 구하는 문제입니다.
이 문제에서 저는 Segment Tree Lazy를 사용했고, 트리에는 해당 숫자를 몇 번 사용할 수 있는지 카운팅을 해줍니다.
1 ~ 5가 있다면
1은 1번, 2는 2번, 3은 3번, 4는 4번, 5는 5번 사용할 수 있습니다.
5 5 5 5 5가 입력된다면 5에서 수를 5번 고른다는 뜻입니다.
만약 4 4 4 4 4가 입력된다면 5개의 4에서 1 ~ 5를 하나씩 만들 수가 없게 되는거죠.
그렇게 i ~ N을 +1씩 업데이트를 해주고, 각각 노드에서의 최솟값으로 갱신하도록 합니다.
그 다음에는 최초로 주어진 수열에서 1 ~ N을 만들 수 있는지 먼저 확인합니다.
list[i]를 사용한게 되기 때문에 list[i] ~ N의 범위에 -1로 업데이트를 시켜줍니다.
트리를 최솟값으로 저장한 이유는 이 연산 과정에서 해당 값의 카운트가 음수인 경우를 빠르게 캐치하기 위해서입니다.
수열의 모든 수를 대상으로 업데이트가 끝난다면 query 함수를 이용하여 트리의 최솟값을 가져옵니다.
최솟값이 0 이상이면 순열을 만들 수 있고, 음수면 만들 수 없습니다.
다음 할 작업은 idx번째 수를 x로 변경하는 것입니다.
처음에는 위에서 -1로 업데이트를 한걸 되돌려야 하는지 고민했었는데 결과적으로 시간초과가 뜨더라고요!
N은 20만, M은 50만이기 때문에 시간초과가 당연한거였습니다.
20만개의 수를 50만번 업데이트 해야되니까요.. ㅎ
좀더 고민했을때는 트리에는 수열에 대한 카운팅이 각각 진행된 상태였고,
어차피 업데이트되는 idx번째 수에 대해서만 카운팅을 바꿔주면 된다는 결론이 나왔습니다.
그래서 수를 업데이트 하기 전에 기존 list[idx]의 범위에 대한 업데이트를 +1로 진행해주고,
새로운 값인 x의 범위에 대한 업데이트를 -1으로 진행해주면 새로운 수열에서의 카운팅 작업이 완료되는 것입니다.
마지막에는 업데이트된 트리의 최솟값을 가져와서 0 이상이면 `TAK`을, 음수면 `NIE`를 출력해주시면 되겠습니다.
|
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
|
#include <iostream>
#include <algorithm>
#define MAX 200001
using namespace std;
int list[MAX];
int tree[MAX << 2];
int lazy[MAX << 2];
int N, M;
void lazyUpdate(int node, int l, int r) {
if (!lazy[node]) return;
tree[node] += lazy[node];
if (l != r) {
lazy[node << 1] += lazy[node];
lazy[(node << 1) + 1] += lazy[node];
}
lazy[node] = 0;
}
int update(int node, int l, int r, int s, int e, int diff) {
lazyUpdate(node, l, r);
if (l > e || s > r) return tree[node];
if (s <= l && r <= e) {
lazy[node] += diff;
lazyUpdate(node, l, r);
return tree[node];
}
int m = (l + r) >> 1;
return tree[node] = min(update(node << 1, l, m, s, e, diff), update((node << 1) + 1, m + 1, r, s, e, diff));
}
int query(int node, int l, int r, int s, int e) {
lazyUpdate(node, l, r);
if (l > e || s > r) return 0;
if (s <= l && r <= e) return tree[node];
int m = (l + r) >> 1;
return min(query(node << 1, l, m, s, e), query((node << 1) + 1, m + 1, r, s, e));
}
void init() {
for (int i = 1; i <= N; i++) {
update(1, 1, N, i, N, 1);
}
for (int i = 0; i < N; i++) {
update(1, 1, N, list[i], N, -1);
}
}
void print() {
if (query(1, 1, N, 1, N) >= 0) cout << "TAK\n";
else cout << "NIE\n";
}
void func() {
init();
print();
int idx, x;
while (M--) {
cin >> idx >> x;
update(1, 1, N, list[idx - 1], N, 1);
update(1, 1, N, x, N, -1);
list[idx - 1] = x;
print();
}
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
cin >> M;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 4442 빌보의 생일 (0) | 2024.08.01 |
|---|---|
| boj 1517 버블 소트 (0) | 2024.06.16 |
| boj 17131 여우가 정보섬에 올라온 이유 (3) | 2024.04.25 |
| boj 12895 화려한 마을 (0) | 2022.09.07 |
| boj 10167 금광 (0) | 2022.09.02 |