백준[3392] 화성지도

문제 설명

문제 링크

http://icpc.me/3392

풀이

스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다.

모든 점을 x축 기준으로 정렬을 하여 왼쪽부터 쓸면서 값을 구하면 된다.

이때 세그먼트 트리로 y축의 점들을 저장해놓는다. 만약 점이 시작하는 점이라면 세그먼트 트리에 1을 더하고, 끝나는 점이라면 -1을 더하면 된다.

하지만 겹치는 부분의 넓이는 구하면 안되기 때문에 위처럼 저장하여 넓이를 바로 계산하면 문제가 발생한다.

그렇기 때문에 세그먼트 트리를 2개 활용한다.

하나는 구간에 점이 몇개가 있는지를 저장하고, 하나는 점이 있는지 유무만 확인할 수 있게 저장한다.

코드

#include <cstdio>
#include <vector>

using namespace std;
using pii = pair<int, int>;

struct T {
    T(int x, pii y, int finish) : x(x), y(y), finish(finish) {}
    int x;
    pii y;
    int finish;
};

vector<T> v;
int seg[30004 * 4];
int cnt[30004 * 4];

void update(int node, int s, int e, int qs, int qe, int val) {
    if (e < qs || qe < s) return;
    if (qs <= s && e <= qe) {
    	cnt[node] += val;
    } else {
        int mid = (s + e) >> 1;
        update(2 * node, s, mid, qs, qe, val);
        update(2 * node + 1, mid + 1, e, qs, qe, val);
    }
    
    if (cnt[node]) {
    	seg[node] = e - s + 1;
    } else {
        if (s == e) seg[node] = 0;
        else seg[node] = seg[node * 2] + seg[node * 2 + 1];
    }
}

int main() {
    int n; scanf("%d", &n);
    while (n--) {
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
        v.push_back(T(a, {b, d - 1}, 1));
        v.push_back(T(c, {b, d - 1}, -1));
    }
    sort(v.begin(), v.end(), [](T &a, T &b) { return a.x < b.x; });
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        if (i) ans += (seg[1] * (v[i].x - v[i - 1].x));
        update(1, 0, 3e4, v[i].y.first, v[i].y.second, v[i].finish);
    }
    printf("%d", ans);
}