3392 - 화성지도

코드

#include <stdio.h>
#include <tuple>
#include <vector>
#include <algorithm>
#define SIZE (30010 << 2)

using namespace std;

typedef tuple<int, int, int, int> P;

vector<P> p;
int tre[SIZE], cnt[SIZE];

void update(int l, int r, int node, int lo, int hi, int val) {
    if (r < lo || hi < l)
        return;
    if (lo <= l && r <= hi) {
        cnt[node] += val;
    }
    else {
        int mid = (l + r) / 2;
        update(l, mid, node * 2, lo, hi, val);
        update(mid + 1, r, node * 2 + 1, lo, hi, val);
    }
    if (cnt[node])
        tre[node] = r - l + 1;
    else {
        if (l == r)
            tre[node] = 0;
        else
            tre[node] = tre[node * 2] + tre[node * 2 + 1];
    }
}

int main()
{
    int n, i, x1, x2, y1, y2, psize, ans = 0, x, y;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        p.push_back(P(x1, y1, y2, 1));
        p.push_back(P(x2, y1, y2, -1));
    }
    sort(p.begin(), p.end());

    psize = n * 2;
    x = 0;
    y = 0;
    for (i = 0; i < psize; i++) {
        update(0, 30000, 1, get<1>(p[i]), get<2>(p[i]) - 1, get<3>(p[i]));
        if (i + 1 < psize && get<0>(p[i]) == get<0>(p[i + 1]))
            continue;
        ans += y * (get<0>(p[i]) - x);
        x = get<0>(p[i]);
        y = tre[1];
    }

    printf("%d", ans);

    return 0;
}

풀이

• x 에 대해 y1, y2, 시작/종료 를 기록하여 plane sweeping 문제로 변경한다.
• x로 정렬하고 y1 이상 y2 미만에 대해서 count 를 1증가 시킨다
• count 가 1 이상인 영역에 대해 y2 - y1 값을 세그먼트 트리에 기재하고 누적합을 갱신
• 전체 누적합을 조회하고, x의 차이값 만큼 곱하여 누적시키면 답이 나온다.
• lazy propagation 이 필요할 것 같지만, 전체 조회만하기 때문에 구현 할 필요가 없다