https://www.acmicpc.net/problem/3392
처음 보는 세그먼트 트리의 유형에 굉장히 어려움을 겪었다.
밑의 글을 참고해서 풀어보았다.
모든 직사각형의 세로선분과 가로선분으로 생기는 부분을 나누어서 생각하는게 핵심이다.

x축으로 정렬된 vector에는
4개의 선분이 들어가게된다

vector의 0번인덱스부터 2*n-1번 인덱스부터 선분하나하나씩을 처리해주면 된다.




#include <iostream> #include <vector> #include <algorithm> using namespace std; #define MAX_LEAF 30000 class Info { public: int x, y1, y2; bool left; Info() {} Info(int x, int y1, int y2, bool left) { this->x = x; this->y1 = y1; this->y2 = y2; this->left = left; } bool operator < (const Info & b) const { return this->x < b.x; } }; int tree[MAX_LEAF * 4]; int cnt[MAX_LEAF * 4]; void update_tree(int now, int left,int right, int start, int end, int value) { // 범위 체크 if (left > end || right < start) return; // 해당 범위에 들어온다면 현재 cnt를 증가 또는 감소 시켜줌 if (left <= start && end <= right) { cnt[now] += value; } // 범위에 들어올 지언정 " range_update " 를위해 하단 리프노드까지 내려가야 한다. else{ int mid = (start + end) / 2; update_tree(now * 2, left, right, start, mid, value); update_tree(now * 2 + 1, left, right, mid+1, end, value); } // 해당 노드가 0 인데 리프노드라면 그냥 0으로 해주면되고 // 리프노드가 아니라면 ( 왼쪾자식 + 오른쪽자식 ) 이 자신의 cnt가 된다. if (!cnt[now]) { if (start != end) tree[now] = tree[now * 2] + tree[now * 2 + 1]; else tree[now] = 0; } // 만약 자신이 해당범위에 들어와서 위에서 "cnt[now] += value" 로인해 1이상이 되었다면 // 자기 하위의 모든 노드들은 범위에 포함되므로, 끝 - 시작 + 1 이 cnt가 된다. else tree[now] = end - start + 1; } vector<Info> vec; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; for (int i = 0; i < N; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; vec.push_back(Info(x1, y1, y2, true)); vec.push_back(Info(x2, y1, y2, false)); } // x축 정렬 ( for 라인스위핑 ) sort(vec.begin(), vec.end()); Info prev; int ans = 0; for (int i = 0; i < vec.size(); i++) { if (i) ans += (vec[i].x - vec[i - 1].x) * tree[1]; // 왼쪽 선분인경우 : +1, 오른쪽선분인 경우 : -1 int value = (vec[i].left == true) ? 1 : -1; update_tree(1, vec[i].y1, vec[i].y2 - 1, 0, MAX_LEAF - 1, value); } cout << ans << "\n"; }
'알고리즘 > [C++]BOJ' 카테고리의 다른 글
[백준] 2336_굉장한 학생 (C++) (0) | 2019.09.30 |
---|---|
[백준] 5676_음주 코딩 (C++) (0) | 2019.09.30 |
[BOJ]7469_K번째 수(C++) (0) | 2019.09.30 |