【題解】TIOJ 1224 矩形覆蓋面積計算

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

int n, st[1000005<<2], lazy[1000005<<2];
vector <tuple<int, int, int, int>> v;
void push_up(int x, int l, int r){
    if (lazy[x]) st[x] = r-l+1;
    else if (r != l) st[x] = st[x<<1] +st[x<<1|1];
    else st[x] = 0;
}
void update(int x, int l, int r, int ul, int ur, int d){
    if (ul <= l && r <= ur){
        lazy[x] += d;
        push_up(x, l, r);
        return;
    }
    int mid = (l+r)/2;
    if (ul <= mid) update(x<<1, l, mid, ul, ur, d);
    if (mid < ur) update(x<<1|1, mid+1, r, ul, ur, d);
    push_up(x, l, r);
}

int main(){
    cin >> n;
    int l, r, d, u;
    for (int i = 0; i < n; i++){
        cin >> l >> r >> d >> u;
        v.push_back({l, d+1, u, 1});
        v.push_back({r, d+1, u, -1});
    }
    sort(v.begin(), v.end());
    int pre = 0;
    long long ans = 0;
    for (auto [pos, d, u, del]:v){
        if (pos != pre){
            ans += 1LL*(pos-pre)*st[1];
            pre = pos;
        }
        update(1, 1, 1000000, d, u, del);
    }
    cout << ans << "\n";
}