우리는 몇몇 문제를 통해 세그먼트 트리와 스위핑으로 직사각형의 면적 혹은 둘레를 구하는 방법을 알아볼 것이다.
대표적인 문제는 화성 지도가 되겠다.
https://www.acmicpc.net/problem/3392
3392번: 화성 지도
첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30
www.acmicpc.net
스위핑 세그먼트 트리 소개
N개의 직사각형이 주어졌을 때 중복을 고려하여 총면적을 구하는 문제다. 바로 본론으로 들어가 우리는 두 개의 세그먼트 트리를 사용하겠다.
각 세그먼트 트리의 용도는 다음으로 나뉜다.
tree1 := 현재 구간의 선분 길이를 관리하는 트리.
tree2 := 해당 구간이 전부 덮였는지 관리하는 트리. 정상적으로 작동하면 해당 세그먼트 트리는 0 이상의 값만 가지고 있어야 한다.
그러면 이 두 세그트리를 이용한 구간 관리는 다음 코드로 이루어진다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void update(vector<int> &tree1, vector<int> &tree2, int node,
int start, int end, int l, int r, int diff)
{
if (start > r || end < l) return;
if (l <= start && end <= r) tree2[node] += diff;
else
{
int m = start + (end - start) / 2;
update(tree1, tree2, node * 2, start, m, l, r, diff);
update(tree1, tree2, node * 2 + 1, m + 1, end, l, r, diff);
}
if (tree2[node]) tree1[node] = end - start + 1;
else if (start != end) tree1[node] = tree1[node * 2] + tree1[node * 2 + 1];
else tree1[node] = 0;
}
|
cs |
구간 밖을 벗어나면 당연히 return 하고 구간 내에 완벽히 포함하면 tree2에 diff를 반영한다. 여기서 diff는 1 또는 -1이다.
이렇게 tree2를 먼저 갱신한 다음 3가지 경우에 따라 tree1의 노드 값을 계산할 것이다.
tree2[node]의 값이 1 이상: 해당 구간이 끊어진 부분 없이 선분으로 완전히 뒤덮였다. 따라서 tree1에 저장할 선분의 길이는 end - start + 1이다.
tree2[node]의 값이 0인데 start != end: 이 경우 비록 선분이 끊어져 있을 수 있으므로 자식 노드들에게 값을 가져와 계산한다.
그 외: 자식도 없고 채워져 있지도 않다. 따라서 길이는 0이다.
이걸로 화성 지도 풀기
뭐 대충 선분을 구하는 건 알겠는데 이걸로 어떻게 면적을 구할지는 감이 잘 안 온다. 우리는 한축을 고정하고 다른 축을 스위핑 할 것이므로 일단 쿼리를 정리해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
using tiiii = tuple<int, int, int, int>;
int n;
vector<tiiii> query;
for (int i = 0; i < n; i++)
{
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
++a1, ++a2, ++b1, ++b2;
query.emplace_back(a1, b1, b2 - 1, 0);
query.emplace_back(a2, b1, b2 - 1, 1);
}
sort(query.begin(), query.end());
|
cs |
여기서는 x축에서 스위핑하기로 했다. 따라서 네 점의 좌표를 받고 y의 끝 좌표에는 1씩 빼줬다.
이렇게 한 이유는 세그먼트 트리에서 뒤덮은 구간에서 1은 길이 1만큼을 차지한다는 의미이기 때문이다. 예를 들어 4는 4~5를 차지하고 있다는 뜻이 된다. 즉 b2는 y 끝점의 좌표이기 때문에 이를 차지하고 있다는 정보로 바꾸기 위해 1을 뺐다.
추가로 더하는 쿼리일 때 마지막 원소에 0, 빼는 쿼리일 때 1을 넣고 정렬했다. 그래야 항상 더하는 연산이 먼저 오게 된다.
이렇게 정렬하면 쿼리를 이런식으로 처리할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
for (int i = 0; i < query.size(); i++)
{
auto [x, y1, y2, t] = query[i];
if (lastx != -1)
{
int diff = x - lastx;
ll segment = seg1[1];
ans += diff * segment;
}
lastx = x;
if (t == 0)
update(seg1, seg2, 1, 1, 30001, y1, y2, 1);
else
update(seg1, seg2, 1, 1, 30001, y1, y2, -1);
}
|
cs |
여기서 lastx의 초기값은 -1이다.
먼저 현재 쿼리를 가져온다. 이때 lastx가 아니면 어떤 y길이가 lastx부터 x까지 유지되었다는 소리다. 그렇다는 소리는 x축 변의 길이가 x - lastx라는 뜻이고 y축 변의 길이가 현재 세그먼트 트리가 수집한 선분의 길이 seg1[1]라는 뜻이므로 이를 위시한 직사각형의 면적은 둘을 곱한 값이 된다.
이런 식으로 스위핑한 직사각형의 넓이를 구할 수 있게 된다. 다음은 3392 화성 지도를 해결하는 전체 코드이다.
|
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
|
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#include "ext/rope"
using namespace std;
using namespace __gnu_cxx;
using pii = pair<int, int>;
using ll = long long;
using tiiii = tuple<int, int, int, int>;
int n;
vector<tiiii> query;
void update(vector<int> &tree1, vector<int> &tree2, int node,
int start, int end, int l, int r, int diff)
{
if (start > r || end < l) return;
if (l <= start && end <= r) tree2[node] += diff;
else
{
int m = start + (end - start) / 2;
update(tree1, tree2, node * 2, start, m, l, r, diff);
update(tree1, tree2, node * 2 + 1, m + 1, end, l, r, diff);
}
if (tree2[node]) tree1[node] = end - start + 1;
else if (start != end) tree1[node] = tree1[node * 2] + tree1[node * 2 + 1];
else tree1[node] = 0;
}
void solve()
{
cin >> n;
vector<int> seg1(30003 * 4), seg2(30003 * 4);
ll ans = 0;
for (int i = 0; i < n; i++)
{
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
++a1, ++a2, ++b1, ++b2;
query.emplace_back(a1, b1, b2 - 1, 0);
query.emplace_back(a2, b1, b2 - 1, 1);
}
sort(query.begin(), query.end());
int lastx = -1;
for (int i = 0; i < query.size(); i++)
{
auto [x, y1, y2, t] = query[i];
if (lastx != -1)
{
int diff = x - lastx;
ll segment = seg1[1];
ans += diff * segment;
}
lastx = x;
if (t == 0)
update(seg1, seg2, 1, 1, 30001, y1, y2, 1);
else
update(seg1, seg2, 1, 1, 30001, y1, y2, -1);
}
cout << ans;
}
int main()
{
#ifdef LOCAL
//freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
직사각형 둘레 구하기
이 방법으로 당연히 둘레도 구할 수 있다. 물론 넓이가 아니기에 x축과 y축을 대상으로 둘 다 계산해줘야 한다는 점을 인지해야 하고 쿼리 처리를 조금 다르게 해야 한다.
https://www.acmicpc.net/problem/2185
2185번: 직사각형의 합집합
첫째 줄에 직사각형의 개수 N이 주어진다. 다음 N개의 줄에는 각 사각형의 정보를 나타내는 네 정수 x1, y1, x2, y2가 주어진다. 이는 사각형의 대각선으로 마주 보는 두 꼭짓점의 좌표가 (x1, y1), (x2,
www.acmicpc.net
여러 직사각형을 겹쳤을 때 그 둘레를 구하는 문제다. 세그먼트 트리는 위와 동일하게 쓰지만 쿼리를 처리할 때 차이가 있다.
정렬부터 약간 다르다. 이때는 시작하는 변인지 끝나는 변인지가 더 중요하여 우선순위를 위해 해당 변수가 더 앞으로 당겨진다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
for (int i = 0; i < n; i++)
{
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
if (a1 > a2) swap(a1, a2);
if (b2 < b1) swap(b1, b2);
a1 += offset, a2 += offset, b1 += offset, b2 += offset;
query.emplace_back(a1, 0, b1, b2 - 1);
query.emplace_back(a2, 1, b1, b2 - 1);
query2.emplace_back(b1, 0, a1, a2 - 1);
query2.emplace_back(b2, 1, a1, a2 - 1);
}
|
cs |
이렇게 하는 이유는 쿼리를 처리할 때 설명하도록 하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void do_query(vector<tiiii> &q, vector<int> &t1, vector<int> &t2)
{
int last = 0;
for (auto [x, t, y1, y2] : q)
{
if (!t)
update(t1, t2, 1, 1, 20001, y1, y2, 1);
else
update(t1, t2, 1, 1, 20001, y1, y2, -1);
ans += abs(t1[1] - last);
last = t1[1];
}
}
|
cs |
여기서 주목할 것은 11~12번째 줄이다. 코드를 보면 현재 선분의 길이와 바로 직전 선분의 길이의 차를 더하고 있다.
위 정렬 순서를 따르면 x축을 기준으로 스위핑 할 때 다음 계산을 하게 된다.
1번 쿼리일 때 last가 0이므로 해당 선분을 더한다.
2번 쿼리일 때 last는 1번 쿼리의 선분이고 abs(현재 - last) = 0이므로 더해지는 게 없다.
3번 쿼리일 때는 last는 여전히 1번 쿼리의 선분이지만 쿼리 갱신을 하고 나면 작은 사각형의 변만 남으므로 abs(2번 선분 - 3번 선분)의 결과가 더해진다. 그리고 last는 2번 선분의 길이가 된다.
4번 쿼리일 대는 쿼리 갱신을 하면 0이 되고 last는 2번 선분의 길이이므로 4번 선분이 더해진다.
이런 과정을 통해 둘레를 구하게 된다. 정렬 순서가 뒤바뀌면 더해질 값이 0이 된다거나 하니 유의해야 한다.
다음은 해당 문제를 해결하는 CPP 코드이다.
|
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
|
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#include "ext/rope"
using namespace std;
using namespace __gnu_cxx;
using pii = pair<int, int>;
using ll = long long;
#define offset 10001
using tiiii = tuple<int, int, int, int>;
int n;
ll ans = 0;
vector<tiiii> query;
vector<tiiii> query2;
void update(vector<int> &tree1, vector<int> &tree2, int node,
int start, int end, int l, int r, int diff)
{
if (start > r || end < l) return;
if (l <= start && end <= r)
{
tree2[node] += diff;
}
else
{
int m = start + (end - start) / 2;
update(tree1, tree2, node * 2, start, m, l, r, diff);
update(tree1, tree2, node * 2 + 1, m + 1, end, l, r, diff);
}
if (tree2[node]) tree1[node] = end - start + 1;
else
{
if (start != end) tree1[node] = tree1[node * 2] + tree1[node * 2 + 1];
else tree1[node] = 0;
}
}
void do_query(vector<tiiii> &q, vector<int> &t1, vector<int> &t2)
{
int last = 0;
for (auto [x, t, y1, y2] : q)
{
if (!t)
update(t1, t2, 1, 1, 20001, y1, y2, 1);
else
update(t1, t2, 1, 1, 20001, y1, y2, -1);
ans += abs(t1[1] - last);
last = t1[1];
}
}
void solve()
{
cin >> n;
vector<int> seg1(20003 * 4), seg2(20003 * 4), seg3(20003 * 4), seg4(20003 * 4);
for (int i = 0; i < n; i++)
{
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
if (a1 > a2) swap(a1, a2);
if (b2 < b1) swap(b1, b2);
a1 += offset, a2 += offset, b1 += offset, b2 += offset;
query.emplace_back(a1, 0, b1, b2 - 1);
query.emplace_back(a2, 1, b1, b2 - 1);
query2.emplace_back(b1, 0, a1, a2 - 1);
query2.emplace_back(b2, 1, a1, a2 - 1);
}
sort(query.begin(), query.end());
sort(query2.begin(), query2.end());
do_query(query, seg1, seg2);
do_query(query2, seg3, seg4);
cout << ans;
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
좌표 압축
그러면 좌표가 매우 커지면 어떻게 될까?
https://www.acmicpc.net/problem/7626
7626번: 직사각형
첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나
www.acmicpc.net
이런 범위가 큰 경우는 길이 계산이 매우 어려워진다. 따라서 좌표 압축을 해야 할 건데 화성 지도를 풀 때 언급한 "구간에서 1은 길이 1만큼을 차지한다는 의미"를 살려야 한다.
화성 지도를 풀 때는 선분의 길이를 구할 때 end - start + 1을 해줬지만 이번에는 좌표 압축을 신경 써줘야 한다.
그냥 좌표 복원하는 함수를 f라고 했을 때 f(end) - f(start) + 1 하면 안되나요? 라고 말할 수 있겠지만 되지 않는다. 사실 왜 안 되는지는 지금도 모른다. 알고 있다면 제보 부탁드린다.
아무튼 위 문제를 해결하기 위해 좌표를 하나 더 추가할 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
|
for (int i = 0; i < n; i++)
{
int a1, b1, a2, b2;
cin >> a1 >> a2 >> b1 >> b2;
crd.push_back(b1);
crd.push_back(b2 - 1);
crd.push_back(b2);
query.emplace_back(a1, 0, b1, b2 - 1);
query.emplace_back(a2, 1, b1, b2 - 1);
}
|
cs |
crd가 좌표압축용 벡터인데 b2와 b2 - 1 둘 다 삽입하는 것을 볼 수 있다. 이렇게 하면 선분의 길이를 구할 때는 단순히 f(end + 1) - f(start)로 잘 구할 수 있게 된다.(f(end)는 b2 - 1, f(end + 1)은 b2가 됨을 생각하자.) 자세한 사항은 밑의 정답 코드를 살펴보도록 하자.
|
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using tiiii = tuple<int, int, int, int>;
int n;
int m;
int inv[600003];
vector<int> crd;
vector<tiiii> query;
int get_idx(int val)
{
return lower_bound(crd.begin(), crd.end(), val) - crd.begin() + 1;
}
void update(vector<ll> &t1, vector<int> &t2, int node,
int start, int end, int l, int r, int diff)
{
if (start > r || end < l) return;
if (l <= start && end <= r)
{
t2[node] += diff;
}
else
{
int m = start + (end - start) / 2;
update(t1, t2, node * 2, start, m, l, r, diff);
update(t1, t2, node * 2 + 1, m + 1, end, l, r, diff);
}
if (t2[node])
{
t1[node] = (ll)inv[end + 1] - inv[start];
}
else if (start != end)
{
t1[node] = t1[node * 2] + t1[node * 2 + 1];
}
else
{
t1[node] = 0;
}
}
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int a1, b1, a2, b2;
cin >> a1 >> a2 >> b1 >> b2;
crd.push_back(b1);
crd.push_back(b2 - 1);
crd.push_back(b2);
query.emplace_back(a1, 0, b1, b2 - 1);
query.emplace_back(a2, 1, b1, b2 - 1);
}
sort(query.begin(), query.end());
sort(crd.begin(), crd.end());
crd.erase(unique(crd.begin(), crd.end()), crd.end());
m = crd.size();
for (int i = 0; i < crd.size(); i++)
{
inv[i + 1] = crd[i];
}
vector<ll> tree1((m + 1) * 4);
vector<int> tree2((m + 1) * 4);
ll ans = 0;
ll lastx = -1;
for (int i = 0; i < query.size(); i++)
{
auto [x, t, y1, y2] = query[i];
y1 = get_idx(y1);
y2 = get_idx(y2);
if (lastx != -1)
{
ll gap = x - lastx;
ans += gap * tree1[1];
}
lastx = x;
int df;
if (!t) df = 1;
else df = -1;
update(tree1, tree2, 1, 1, m, y1, y2, df);
}
cout << ans;
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}
|
cs |
지금까지 2차원 좌표계에서 세그먼트 트리로 직사각형과 관련된 연산을 하는 법을 알아보았다. 아주 흥미로운 주제인데 연습 문제가 많이 없는 것 같아서 아쉽다. 그래도 지금까지 모은 문제를 문제집으로 공유하니 문제 풀이를 통해 감각을 익혀갔으면 좋겠다.
https://www.acmicpc.net/workbook/view/10823
문제집: 직사각형 (herdson)
www.acmicpc.net
'CP Algorithm & Knowledge' 카테고리의 다른 글
| 2차원 평면에서 모든 점 쌍의 유클리드 거리 합 구하기 (0) | 2022.09.11 |
|---|---|
| Dynamic Segment Tree and Lazy Propagation (0) | 2022.09.06 |
| KMP 알고리즘으로 부분 문자열 효과적으로 제거하기 (0) | 2022.07.23 |
| 매내처 알고리즘(Manacher's algorithm) (0) | 2022.07.20 |
| KMP(Knuth Morris Pratt) 알고리즘 복습 노트 (0) | 2022.07.15 |
