【模板】扫描线 & 矩形面积并(Scanline and Rectangle Union Area)

求 $n$ 个四边平行于坐标轴的矩形的面积并。

第一行一个正整数 $n$ 。

接下来 $n$ 行每行四个非负整数 $x_1, y_1, x_2, y_2$ ，表示一个矩形的四个端点坐标为 $(x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)$ 。

一行一个正整数，表示 $n$ 个矩形的并集覆盖的总面积。

2
100 100 200 200
150 150 250 255

对于 $20\%$ 的数据， $1 \le n \le 1000$ 。
对于 $100\%$ 的数据， $1 \le n \le {10}^5$ ， $0 \le x_1 < x_2 \le {10}^9$ ， $0 \le y_1 < y_2 \le {10}^9$ 。

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	20	2~7	小规模 n≤1000 / 特殊: 单一满域矩形面积10^18检验64位整数 / 特殊: 完全重合与共边相邻矩形
2	20	8~13	中等规模 n≤20000 / Hack: 同一横坐标处多条入边与出边同时触发的扫描线顺序检验
3	25	14~19	大规模 n=100000 网格纵横交错十字条带扫描线+线段树测试
4	25	20~25	满规模 n=100000,坐标≤10^9 离散化极限压力测试

出处：原题链接

#P5490. 【模板】扫描线 & 矩形面积并(Scanline and Rectangle Union Area)