【題解】ZeroJudge e886: Q4 覆蓋總面積

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

int l, d, r, u, st[1000005<<2], lazy[1000005<<2];
vector <tuple<int, int, int, int> > v;

void pull(int x, int l, int r){
    if (lazy[x]) st[x] = r-l+1;
    else if (l != r) 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 del){
    if (ul <= l && r <= ur){
        lazy[x] += del;
        pull(x, l, r);
        return;
    }
    int mid = (l+r)/2;
    if (ul <= mid) update(x<<1, l, mid, ul, ur, del);
    if (mid < ur) update(x<<1|1, mid+1, r, ul, ur, del);
    pull(x, l, r);
}

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