알고리즘/BOJ 문제풀이
[Sweeping] BOJ 7626 직사각형
4Legs
2021. 2. 4. 01:12
문제 링크 : www.acmicpc.net/problem/7626
위 문제와 동일한 풀이법을 가지지만, y좌표의 범위가 10억까지기 때문에 좌표 압축이 필요한 문제이다.
각 y좌표를 좌표값이 아닌 인덱스로 나타내어, 이 인덱스로 세그먼트 트리를 구성한다.
그러면 1-10^9의 구간을 가지는 세그먼트 트리를 1-200,000 구간의 세그먼트 트리로 압축할 수 있다.
코드의 39번째 줄처럼 1 이상인 노드를 찾았을 때 y좌표의 개수를 세 주는 과정을 인덱스 참조로 변경해주어야 올바른 답을 구할 수 있다.
[코드]
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
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXSIZE 400001
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
typedef struct vert {
int x;
p y;
bool start;
}vert;
int n;
ll segtree[MAXSIZE * 4];
ll cnt[MAXSIZE * 4];
vector<vert> verts;
vector<int> ylist;
void update_range(int node, int start, int end, int l, int r, int val) {
if (l > end || r < start) return; //범위를 벗어난 경우
if (l <= start && end <= r) {
//완전히 포함되는 경우
cnt[node] += val;
}
else {
//범위가 걸치는 경우
int mid = (start + end) / 2;
update_range(node * 2, start, mid, l, r, val);
update_range(node * 2 + 1, mid + 1, end, l, r, val);
}
if (cnt[node]) {
segtree[node] = (ll)ylist[end] - ylist[start - 1];
}
else {
if (start == end) segtree[node] = 0;
else segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}
}
ll get_answer() {
ll ret = 0;
int diff_x = 0, diff_y;
for (int i = 0; i < verts.size(); i++) {
if (i > 0) {
diff_x = verts[i].x - verts[i - 1].x;
//diff_y = verts[i].y.second - verts[i].y.first;
ret += segtree[1] * diff_x;
}
int val = verts[i].start == true ? 1 : -1;
int y1_idx = lower_bound(ylist.begin(), ylist.end(), verts[i].y.first) - ylist.begin();
int y2_idx = lower_bound(ylist.begin(), ylist.end(), verts[i].y.second) - ylist.begin();
update_range(1, 1, ylist.size(), y1_idx + 1, y2_idx, val);
}
return ret;
}
vert create_vert(int x, int y1, int y2, bool start) {
vert temp;
temp.x = x;
temp.y.first = y1; temp.y.second = y2;
temp.start = start;
return temp;
}
bool cmp_vert(vert a, vert b) {
return a.x < b.x;
}
void init() {
int x1, x2, y1, y2;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x1 >> x2 >> y1 >> y2;
verts.push_back(create_vert(x1, y1 + 1, y2 + 1, true));
verts.push_back(create_vert(x2, y1 + 1, y2 + 1, false));
ylist.push_back(y1 + 1);
ylist.push_back(y2 + 1);
}
sort(ylist.begin(), ylist.end());
ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
sort(verts.begin(), verts.end(), cmp_vert);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(NULL);
init();
ll answer = get_answer();
printf("%lld\n", answer);
return 0;
}
|
cs |