# [Platinum II] 화성 지도 #### [문제 링크](https://www.acmicpc.net/problem/3392) ## 문제 설명 <p>2051년, 야심차게 발사한 화성탐사선 성화가 탐사한 곳의 화성 지도를 N개 보냈다.</p> <p>화성탐사선의 성공에 의기양양해진 BaSA(Baekjoon Space Agency)는 야심찬 계획을 발표했다.</p> <p>화성 전체 지도를 만들겠습니다!</p> <p>전체 지도를 만들기 전에, 지금까지 화성탐사선이 보낸 지도를 모두 합쳤다. 이때, 이 지도의 크기는 몇일까?</p> <p>탐사선이 보낸 지도는 항상 직사각형 모양이며, 겹칠 수도 있다.</p> ## 입력 <p>첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000)으로 이루어져 있다. (x1, y1)와 (x2, y2)은 직사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표이다. 모든 지도는 직사각형이고, 변은 항상 x축과 y축에 평행하다.</p> ## 출력 <p>첫째 줄에 지금까지 탐사선이 보낸 지도를 모두 합쳤을 때, 그 면적을 출력한다. (직사각형을 모두 합쳤을 때 면적)</p> ## 풀이 #### x좌표를 기준으로 오름차순으로 정렬하고, 사각형의 y좌표를 범위 업데이트 하면서 총 면적을 구하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 30000; int _size=1, arr[MAX*3], cnt[MAX*3]; struct vertical_line { int x, y1, y2, val; }; void updateRange(int L, int R, int nodeNum, int nodeL, int nodeR, int val) { if(R<nodeL || nodeR<L) return; if(L<=nodeL && nodeR<=R) { cnt[nodeNum] += val; } else { int mid = (nodeL+nodeR)/2; updateRange(L, R, nodeNum*2, nodeL, mid, val); updateRange(L, R, nodeNum*2+1, mid+1, nodeR, val); } if(cnt[nodeNum]) arr[nodeNum] = (nodeR-nodeL+1); else if(nodeL==nodeR) arr[nodeNum]=0; else arr[nodeNum] = arr[nodeNum*2] + arr[nodeNum*2+1]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(_size<MAX) _size<<=1; _size<<=1; vector<vertical_line> v; while(n--) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; v.push_back({x1, y1, y2, 1}); v.push_back({x2, y1, y2, -1}); } sort(v.begin(), v.end(), [](auto a, auto b){ return a.x < b.x; }); long long total=0, last=0; for(auto l:v) { total += arr[1]*(l.x-last); updateRange(l.y1, l.y2-1, 1, 0, _size/2-1, l.val); last = l.x; } cout << total; } ```