BOJ 7626 직사각형

1 개요[ | ]

BOJ 7626 직사각형
2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 2e5;
struct Line {
    ll x, y1, y2, val;
    bool operator < (const Line& p) { return x < p.x; }
};
int N;
Line arr[2 * MAXN + 10];
vector<ll> comp;

struct SegTree {
    int n;
    vector<ll> sum, cnt;
    SegTree(int n) : n(n), sum(4 * n + 10), cnt(4 * n + 10) {}

    void update(int node, int tl, int tr, int l, int r, ll val) {
        if (tr < l || r < tl) return;
        if (l <= tl && tr <= r) {
            cnt[node] += val;
            if (cnt[node] != 0) sum[node] = comp[tr] - comp[tl - 1];
            else {
                if (tl != tr) sum[node] = sum[node * 2] + sum[node * 2 + 1];
                else sum[node] = 0;
            }
            return;
        }
        int mid = tl + tr >> 1;
        update(node * 2, tl, mid, l, r, val);
        update(node * 2 + 1, mid + 1, tr, l, r, val);

        if (cnt[node] != 0) sum[node] = comp[tr] - comp[tl - 1];
        else {
            if (tl != tr) sum[node] = sum[node * 2] + sum[node * 2 + 1];
            else sum[node] = 0;
        }
    }

    ll query() { return sum[1]; }
};

void solve() {
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    sort(arr, arr + N * 2);
    SegTree st(comp.size() - 1);
    ll bef = arr[0].x;
    ll answer = 0;
    for (int i = 0; i < N * 2; i++) {
        answer += (arr[i].x - bef) * st.query();
        bef = arr[i].x;
        st.update(1, 1, comp.size() - 1, lower_bound(comp.begin(), comp.end(), arr[i].y1) - comp.begin() + 1,
                   lower_bound(comp.begin(), comp.end(), arr[i].y2) - comp.begin(), arr[i].val);
    }
    cout << answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        ll x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        arr[i * 2] = {x1, y1, y2, 1};
        arr[i * 2 + 1] = {x2, y1, y2, -1};
        comp.push_back(y1);
        comp.push_back(y2);
    }
    solve();
}