题解

思路

矩形面积并可以沿横坐标分成若干竖条；关键是求每个竖条内被覆盖的纵向总长度。小规模时直接枚举压缩单元格，中等规模时使用二维差分，满分算法则用扫描线和线段树动态维护纵向并长。

做法

以下按子任务给出由直接枚举到满分扫描线的实现层级。

子任务 1：单元格枚举

收集所有矩形的横、纵坐标并分别排序去重。任意相邻横坐标与相邻纵坐标围成的开矩形内部，覆盖它的原矩形集合不会改变。枚举每个这样的单元格，再枚举全部矩形判断它是否被覆盖；若被覆盖，就把单元格面积加入答案。坐标数均为 $O(n)$，复杂度为 $O(n^3)$，可处理 $n\le30$。

子任务 2：整数网格二维差分

当全部坐标不超过 $1000$ 时，在整数单位方格上建立二维差分。每个矩形对差分数组的四个角作加减，二维前缀和恢复每个单位方格的覆盖次数。覆盖次数为正的单位方格各贡献面积 $1$。复杂度为 $O(n+C^2)$，其中 $C\le1000$。

子任务 3：坐标压缩后二位差分

把所有横、纵边界分别压缩，在压缩网格上对每个矩形做二维差分。恢复覆盖次数后，压缩单元格 $(i,j)$ 的实际面积是相邻横坐标差与相邻纵坐标差之积。网格规模为 $O(n^2)$，时间和空间复杂度均为 $O(n^2)$。

子任务 4：扫描线与线段树

把每个矩形拆成两条竖直事件：在 $x_1$ 处加入纵区间 $[y_1,y_2)$，在 $x_2$ 处删除该区间。按横坐标排序事件，并压缩全部纵坐标。

线段树维护每个纵坐标基本区间被当前活动矩形覆盖的次数以及整个结点区间的实际覆盖长度。若结点覆盖次数为正，覆盖长度就是该结点代表的完整纵坐标长度；否则叶结点长度为零，非叶结点长度为两个儿子长度之和。

处理同一横坐标的一组事件前，当前覆盖纵向总长度在上一横坐标到当前横坐标之间保持不变，因此把“横坐标差乘当前覆盖长度”加入答案，再应用该横坐标的所有加入和删除事件。每个事件在线段树上修改一次，总复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

正确性证明

扫描线在两个相邻事件横坐标之间不会穿过任何矩形竖边，所以活动矩形集合不变。线段树依据覆盖次数递归维护这些活动矩形纵区间的并长，因而根结点长度恰是该竖条内被至少一个矩形覆盖的纵向长度。该长度乘竖条宽度就是并集在此竖条内的面积。所有竖条内部互不相交且完整划分矩形并集的横向范围，把它们的面积求和便得到全部矩形的面积并。

边界与实现要点

• 区间按半开形式 $[y_1,y_2)$ 处理，相邻矩形公共边不会产生面积。
• 同一横坐标的事件必须在结算上一竖条后一起处理。
• 坐标差与最终面积可能达到 $10^{18}$，应使用 64 位整数。

复杂度

四个层级的时间复杂度依次为 $O(n^3)$、$O(n+C^2)$、$O(n^2)$ 与 $O(n\log n)$；对应空间复杂度依次为 $O(n)$、$O(C^2)$、$O(n^2)$ 与 $O(n)$。