백준[7626] 직사각형

문제 설명

문제 링크

http://icpc.me/7626

풀이

백준[3392] 화성지도 이 문제와 거의 유사하다.

위 문제와 풀이는 모두 동일한데 값의 범위가 매우 크기 때문에 좌표압축을 해야한다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll MAX = 4e5 + 5;

struct T {
    T(ll x, pll y, ll finish) : x(x), y(y), finish(finish) {}
    ll x;
    pll y;
    ll finish;
};

vector<T> v;
vector<ll> ySet;
ll seg[MAX * 4];
ll cnt[MAX * 4];

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

int main() {
    ll n; scanf("%lld", &n);
    while (n--) {
        ll a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        v.push_back(T(a, {c + 1, d + 1}, 1));
        v.push_back(T(b, {c + 1, d + 1}, -1));
        ySet.push_back(c + 1);
        ySet.push_back(d + 1);
    }

    sort(ySet.begin(), ySet.end());
    ySet.erase(unique(ySet.begin(), ySet.end()), ySet.end());
    sort(v.begin(), v.end(), [](T &a, T &b) { return a.x < b.x; });

    ll ans = 0;
    for (ll i = 0; i < v.size(); i++) {
        if (i) ans += (seg[1] * (v[i].x - v[i - 1].x));
        ll qs = lower_bound(ySet.begin(), ySet.end(), v[i].y.first) - ySet.begin();
        ll qe = lower_bound(ySet.begin(), ySet.end(), v[i].y.second) - ySet.begin();
        update(1, 1, MAX, qs + 1, qe, v[i].finish);
    }
    printf("%lld", ans);
}