- Dynamic Programming
- 백준
- 알고리즘
- 세그먼트 트리
- 2023 SW - IT Contest
- BOJ 31226
- 27173
- 27114
- BOJ 30029
- Sakura Reflection
- 충남대학교 2023 SW - IT
- 냅색
- fortune's algorithm
- boj23054
- BOJ 30027
- boj 30788
- voronoi diagram
- 느리게 갱신되는 세그먼트 트리
- 누텔라트리(hard)
- dx dy
- CodeForces
- 컴퓨터융합학부
- 오일러투어트리
- BOJ 30026
- BOJ 30028
- 수열과 쿼리 43
- BOJ17139
- Delaunay triangulation
- 2023 Engineering Pair
- hhs2003
알고리즘 일지
BOJ 10070 - 벽 본문
문제 링크
문제 풀이
1번 쿼리는 지정된 높이 미달인 벽이 있으면 그 높이까지 벽을 쌓아주는 쿼리이다. 요약하면,
$1$ $l$ $r$ $h$ 에 대하여, $A_i := max(A_i, h)$ $(l \leq i \leq r)$를 수행한다.
2번 쿼리는 지정된 높이를 초과하는 벽이 있으면, 그 높이까지 벽을 없애주는 쿼리이다. 요약하면,
$2$ $l$ $r$ $h$ 에 대하여, $A_i := min(A_i, h)$ $(l \leq i \leq r)$를 수행한다.
이렇게 발생의 전환을 하면 바로, 머리속에서 풀이가 떠오르는 독자들도 있을 것이고, 아닌 독자들도 있을 것이다.
뭔가 알 것 같다면, 페이지를 내리고 스스로 생각해보는 것을 추천한다.
일단 출력은 마지막에 한번 하니까, 세그먼트 트리의 Lazy Propagation을 응용해서 Lazy에 잘 쌓아놓은 다음에, 출력하기전 모든 노드를 한번씩 전파하면 된다.
하지만, 종류가 다른 쿼리가 2개여서, 이 문제의 핵심은 어떻게 propagation을 해야 할지가 된다.
편하게 구간 $[l, r]$에 대해, min처리에 필요한 값을 ${MN}_{l, r}$, max처리에 필요한 값을 $MX_{l, r}$ 이라고 하겠다.
그리고 마지막에, 노드 한개에 대해서, $A_i = max(A_i, MX_{i, i})$ 그리고 $A_i = min(A_i, MN_{i, i})$ 를 적용해준다고 하자.
적용하는 순서를 신경쓰는 사람이 있을텐데, 그것을 해결하는 것이 문제다. 지금부터 풀어가보도록 하자.
독자들이 직접 관찰해 보면 알겠지만, 쿼리가 무시 당하는 때가 있고, 기존 쿼리에 의해 덮어지는 경우도 있다는 것을 관찰 할 수 있었을 것이다.
예를 들어, $A_i$ 에 $max(3)$ 쿼리를 날리고, $min(1)$ 쿼리를 날리면, 결과적으로 $A_i$는 1이 된다. 즉 기존에 있던 lazy가 서로 다른 쿼리에 의해 무시된다.
어떠한 적당한 구간 $[l, r]$에 대하여, 해당구간에 $min(10)$ 과, $max(5)$를 날리면, 동시에 두 값을 가지고 있어야 하고, 둘다 무시하면 안된다는 것을 알 수 있다. 그럼 $MN_{l, r} = 10 $ 이고, $MX_{l, r} = 5$ 이다.
이 상태에서, $max(6)$을 날리면 $MX_{l, r} = 6$ 으로 바꾸어 주면 되지만, $max(4)$일 경우, 그러면 안된다는 것을 쉽게 볼 수 있다. 이 쿼리는 무시 해야만 하며, 갱신 될 경우, 지정된 값만큼 벽을 오히려 못쌓아버리는 대참사가 일어나게 된다.
$max(11)$을 날리면, $MX_{l, r} = 11$로 해주면 괜찮다. 하지만, 해당 구간에서 관리하는 두개의 값이,
$MX_{l ,r} = 11$, $MN_{l, r} = 10$ 인데,
적용 하는 순서에 따라서 해당 구간의 값이 달라지는 기괴한 현상이 일어나게 된다.
이부분을 아트하게 설계하는 것이 난관이다.
어떻게 해결 해야 할까?
일단 위의 상황에서는, 결국 구간 $[l, r]$ 이 모두 11이므로, $MN_{l, r}$ 값도 11로 만들면 마지막에 적용했을 때, 모든 구간이 11로 바뀌게 된다.
즉 전파 과정에서, 동적으로 lazy값을 수정해야 한다는 것이다.
전파 할 때, 이미 lazy되어 있는 값을 이용하여, 미리 계산해놓으면 된다.
전파 할때, 전파 대상의 Lazy칸에 있는 값에 max와 min을 갱신하면서, 계산하면 된다.
위와 같은 경우에서는, $MX$ 값을 전파할 때, 전파 당하는 $MX$ 와 $MN$을 갱신시켜나가면 된다.
lazy값에 다가 $MN$과 $MX$를 전파 할 때, 크기를 비교하여 더 작거나 더 큰값을 갱신시켜주면 되는데, 이때, 중요한 건 서로의 값에도 전파할 때, 더큰 값과 더 작은 값을 비교하여 갱신시켜나가주면 된다.
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
|
#include<bits/stdc++.h>
#define MAX 2020202
#define MAX_T 8080808
#define INF 1e8
using namespace std;
int N, K, A, x, y, m, h;
int mx[MAX_T], mn[MAX_T], re[MAX_T], ans[MAX_T];
void push (int n, bool p) {
if (!re[n]) return;
if (p) {
re[n << 1] = re[n<< 1 | 1] = 1;
mx[n << 1] = max(mx[n << 1], mx[n]);
mn[n << 1] = max(mn[n << 1], mx[n]);
mx[n << 1] = min(mx[n << 1], mn[n]);
mn[n << 1] = min(mn[n << 1], mn[n]);
mx[n << 1 | 1] = max(mx[n << 1 | 1], mx[n]);
mn[n << 1 | 1] = max(mn[n << 1 | 1], mx[n]);
mx[n << 1 | 1] = min(mx[n << 1 | 1], mn[n]);
mn[n << 1 | 1] = min(mn[n << 1 | 1], mn[n]);
} else {
ans[n] = min(mn[n], ans[n]);
ans[n] = max(mx[n], ans[n]);
}
re[n] = mx[n] = 0;
mn[n] = INF;
}
void query (int node, int s, int e, int left, int right) {
push(node, left != right);
if (right < s || e < left) return;
if (s <= left && right <= e) {
if (m == 1) mx[node] = h;
else mn[node] = h;
re[node] = 1;
return;
}
int mid = left + right >> 1;
query(node << 1, s, e, left, mid);
query(node << 1 | 1, s, e, mid+1, right);
}
void answer (int node, int s, int e) {
push(node, s != e);
if (s == e) {
cout << ans[node] << '\n';
return;
}
int mid = s + e >> 1;
answer(node << 1, s, mid);
answer(node << 1 | 1, mid+1, e);
}
int main () {
cin.tie(0);ios_base::sync_with_stdio(0);
cin >> N >> K;
fill(mn, mn+MAX_T, INF);
for (int i=0;i<K;i++) {
cin >> m >> x >> y >> h;
query(1, x, y, 0, N-1);
}
answer(1, 0, N-1);
}
|
cs |
'알고리즘 풀이' 카테고리의 다른 글
BOJ 27989 - 가장 큰 증가하는 부분 수열 2 (0) | 2023.05.12 |
---|---|
BOJ 27173 - 수열과 쿼리 43 (0) | 2023.01.13 |
BOJ 27114 - 조교의 맹연습 (dx dy 테크닉에 대하여) (0) | 2023.01.09 |
내가 배운 알고리즘/이론 정리 (1) | 2022.12.20 |
22.12.20일 전까지의 기록 (0) | 2022.12.20 |