扫描线问题

解题思路：

本题要求若干个矩形的面积并，所有矩形的面积并可能是一个不规则图形，我们没办法直接去求。

这里需要用到扫描线来帮助我们求面积并，我们将整个平面根据所有点的横坐标划分成若干个长条区域。此时所有的顶点都一定在每个区域的边界上，这样就能保证每个区域中要么没有面积并，要么有若干块矩形面积并，且这些矩形的宽度和所在区域的宽度相同。

此时每个区域的宽度都是已知的，我们只需要求一下每个长条区域中所有矩形的总长度，此时宽度乘上总长度，就是这个区域中所有矩形的面积和，将每个区域中的矩形的面积加在一起就是所有矩形的总面积。

这就是一个最简单的扫描线的问题，由于本题数据范围很小，因此每个区域中所有矩形的总长度可以直接枚举所有矩形来求，如果数据范围很大的话，则可以考虑用线段树来维护每个区域中所有矩形的总长度。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010;

int n;
PII l[N], r[N]; //存储每个矩形的左下角和右上角
vector<int> xs; //存储所有横坐标
PII q[N]; //存储当前区域中所有矩形的高度区间

LL range_area(int a, int b) //计算横坐标在 [a, b] 中的矩形面积
{
    int cnt = 0; //记录当前区域中的矩形数量
    for(int i = 0; i < n; i++)
        if(l[i].first <= a && r[i].first >= b)
            q[cnt++] = {l[i].second, r[i].second};

    if(!cnt) return 0; //如果当前区域中没有面积，直接返回

    sort(q, q + cnt); //否则将所有高度区间左、右端点从小到大排序

    LL res = 0; //记录当前区域中所有矩形的总高度
    int st = q[0].first, ed = q[0].second;
    for(int i = 1; i < cnt; i++)
        if(q[i].first <= ed) ed = max(ed, q[i].second); //区间合并
        else
        {
            res += ed - st;
            st = q[i].first, ed = q[i].second;
        }
    res += ed - st; //加上最后一个区间
    return res * (b - a); //返回当前区间中所有矩形的总面积
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d%d%d", &l[i].first, &l[i].second, &r[i].first, &r[i].second);
        xs.push_back(l[i].first);
        xs.push_back(r[i].first);
    }

    //排序并判重
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    LL res = 0; //记录总面积
    for(int i = 0; i + 1 < xs.size(); i++) res += range_area(xs[i], xs[i + 1]); //累加每个区域的面积
    printf("%lld\n", res);

    return 0;
}