一、扫描线

扫描线一般用于图形类的计算，用数据结构辅助在图形上扫来扫去，比如计算矩形面积并，周长并，二位数点等问题。

二、Atlantis 问题 / 矩形面积并

https://www.luogu.com.cn/problem/P5490

先挂张图（明显是 OI-wiki 的）：

算法原理很简单，就是扫描一下每一个纵坐标 \(y\)（矩阵的边界），其对应在矩形并中有贡献的长度，然后累加即可。

比如说上面的动图，将矩形并分成 \(5\) 段，每一段都对应纵坐标的一段区间，然后再乘以在矩形并里的长度，算出这一段的面积然后累加即可。

Q：每一段的底边长度怎么维护？

A：用线段树，每加入 / 删除一个矩形就在线段树的对应区间更新即可。

然后就是纵坐标从小到大扫一遍。

如果范围很大就离散化。