【題解】HDU 1255 覆盖的面积

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

int t, n, lazy[10005<<2];
double st1[10005<<2], st2[10005<<2];
vector <tuple<double, double, double, int>> v;
vector <double> id;

int get_id(double x){
    return lower_bound(id.begin(), id.end(), x)-id.begin();
}
void push_up(int x, int l, int r){
    if (lazy[x] >= 2) st2[x] = id[r]-id[l-1];
    else if (lazy[x] == 1) st2[x] = st1[x<<1] + st1[x<<1|1];
    else if (r != l) st2[x] = st2[x<<1] +st2[x<<1|1];
    else st2[x] = 0;
    if (lazy[x]) st1[x] = id[r]-id[l-1];
    else if (r != l) st1[x] = st1[x<<1] +st1[x<<1|1];
    else st1[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 >> t;
    while (t--){
        cin >> n;
        double l, r, d, u;
        id.clear();
        v.clear();
        for (int i = 0; i < n; i++){
            cin >> l >> d >> r >> u;
            id.push_back(d);
            id.push_back(u);
            v.push_back(make_tuple(l, d, u, 1));
            v.push_back(make_tuple(r, d, u, -1));
        }
        sort(id.begin(), id.end());
        id.erase(unique(id.begin(), id.end()), id.end());
        sort(v.begin(), v.end());
        double pre = 0, ans = 0;
        for (auto i:v){
            double pos = get<0>(i), d = get<1>(i), u = get<2>(i);
            int del = get<3>(i);
            if (pos != pre){
                ans += (pos-pre)*st2[1];
                pre = pos;
            }
            update(1, 1, id.size()-1, get_id(d)+1, get_id(u), del);
        }
        printf("%.2f\n", ans);
    }
}