给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积. (扫描线 pushup函数升级)

#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
const int N = 100010;

struct Node{
    int l, r;
    int cnt;
    double len, len2;
}tr[N << 2];

struct Segment{
    double x, y1, y2;
    int k;
    bool operator< (const Segment& ver) const
    {
        return x < ver.x;
    }
}seg[N << 1];

int t;
vector<double> alls;
int n;

int find(double x)
{
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r, tr[u].cnt = 0, tr[u].len = 0, tr[u].len2 = 0;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);    
}

void pushup(int u)
{
    if(tr[u].cnt) tr[u].len = alls[tr[u].r + 1] - alls[tr[u].l];
    else if(tr[u].l != tr[u].r) tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    else tr[u].len = 0;

    if(tr[u].cnt >= 2) tr[u].len2 = alls[tr[u].r + 1] - alls[tr[u].l];
    else if(tr[u].cnt == 1) tr[u].len2 = tr[u << 1].len + tr[u << 1 | 1].len;
    else if(tr[u].l != tr[u].r) tr[u].len2 = tr[u << 1].len2 + tr[u << 1 | 1].len2;
    else tr[u].len2 = 0;
}

void modify(int u, int l, int r, int k)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        // printf("cnt = %d\n", tr[u].cnt);
        tr[u].cnt += k;
        pushup(u);
        return ;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, k);
    if(r > mid) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

void solve()
{
    double res = 0;
    for(int i = 0 ; i < 2 * n ; i ++ )
    {
        if(i > 0) res += tr[1].len2 * (seg[i].x - seg[i - 1].x);
        int l = find(seg[i].y1), r = find(seg[i].y2) - 1;
        if(l <= r) modify(1, l, r, seg[i].k);
        // printf("%.2lf %.2lf %.2lf\n", seg[i].y1, seg[i].y2, tr[1].len2);
    }

    printf("%.2lf\n", res);
    return ;
}

int main(void)
{
    scanf("%d", &t);

    while(t -- )
    {
        alls.clear();
        scanf("%d", &n);
        for(int i = 0, idx = 0 ; i < n; i ++ )
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[idx ++] = {x1, y1, y2, 1};
            seg[idx ++] = {x2, y1, y2, -1};
            alls.push_back(y1), alls.push_back(y2);
        }        
        build(1, 0, alls.size());
        sort(seg, seg + 2 * n);
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        solve();
    }
    return 0;
}


/*

1
2
0 0 2 2
1 1 3 3

*/