线段树 + 扫描线 + 离散化 + 二分

时间复杂度分析

建树O(n), 单次查询，修改O(logn), 二分(O(logn)
离散化中 O(n)去重, O(nlogn) 排序
总时间复杂度O(nlogn)

详情见注释 其实是因为懒

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;

struct Segment            // 用来存线段
{
    double x, y1, y2;
    int d;          // 标记它是第一次这一段在前还是在后
    bool operator< (const Segment & A) const
    {
        return x < A.x;      // 按横坐标从小到大排序
    } 

}seg[N << 1];

// 线段树的每个节点 保存长度为1的线段
struct Node
{
    int l, r;
    int tag;      // 记录这段区间出现了几次
    double len;   // 记录这段区间的长度;
}tr[N << 3];
vector<double> ys;

int find(double x)
{
    // 需要返回vector 中第一个 >= x 的数的下标
    return lower_bound(ys.begin(), ys.end(), x) - ys.begin();    // 如果不减，返回的是迭代器， 减之后返回int
}

void push_up(int u)
{
    if (tr[u].tag)    tr[u].len = ys[tr[u].r + 1] - ys[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;
    // 如果此段区间的标记全被删掉了   那么如果它是叶子节点， 直接变为零，  如果不是， 用他的两个儿子来更新它
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        // 因为后面两个都是0, 所以不需要push_up;
    }
}

void modify(int u, int l, int r, int d)
{
    if (l <= tr[u].l && r >= tr[u].r)   
    {
        tr[u].tag += d;
        push_up(u);
        // 扫描线 特殊在 修改[l, r]区间时，只需要修改父节点，不需要push_down操作来更新儿子节点
        // 因为只要父节点的tag > 0    永远没儿子节点什么事
        // 如果父节点的tag == 0, 那么把父节点push_up一下就行， 查询的时候只要输出父节点的长度就行， 同样也没儿子节点什么事
        // 所以即便是修改区间， 也不需要lazt_tag
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)  modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        push_up(u);
    }
}

int main()
{
    int t = 1, n;
    while (scanf("%d", &n), n)
    {
        ys.clear();
        for (int i = 1, j = 0; i <= n; i ++)
        {
            double x1, x2, y1, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[j ++] = {x1, y1, y2, 1};
            seg[j ++] = {x2, y1, y2, -1};
            ys.push_back(y1);
            ys.push_back(y2);
        }

        sort(seg, seg + n * 2);
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        build(1, 0, ys.size() - 2);             // 线段树的每个叶子节点[l, l]， 代表离散化后的y轴上的 [l, l + 1], 所以从零开始初始化;


        double res = 0;
        for (int i = 0; i < 2 * n; i ++)
        {
            if (i)  res += tr[1].len * (seg[i].x - seg[i - 1].x);      // 只需要查询祖宗节点的Len就行，枚举线段即可，因为如果枚举的两条线段x 相同，那么总面积 + 0,不影响，之后当前列 x 全部被 modify 之后，遍历到下一个 x 的一条边时，才会算进去，而且每个区间之后算一次
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].d);
        }
        printf("Test case #%d\n", t ++);
        printf("Total explored area: %.2lf\n\n", res);
    }
    return 0;
}