[Sweeping] BOJ 7626 직사각형

문제 링크 : www.acmicpc.net/problem/7626

7626번: 직사각형

 

[Swipping] BOJ 3392 화성 지도

위 문제와 동일한 풀이법을 가지지만, y좌표의 범위가 10억까지기 때문에 좌표 압축이 필요한 문제이다.

각 y좌표를 좌표값이 아닌 인덱스로 나타내어, 이 인덱스로 세그먼트 트리를 구성한다.

그러면 1-10^9의 구간을 가지는 세그먼트 트리를 1-200,000 구간의 세그먼트 트리로 압축할 수 있다.

코드의 39번째 줄처럼 1 이상인 노드를 찾았을 때 y좌표의 개수를 세 주는 과정을 인덱스 참조로 변경해주어야 올바른 답을 구할 수 있다.

 

[코드]

#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;
}