【学习笔记】扫描线
【别急，我也不会，没写完】
- 定义：
- 求面积并：
定义：
如图：
（图片来源：oiwiki）
像这样的一条线在图上扫描时，便是扫描线。
（呃呃和没说没有任何区别呢）
因此可见扫面线往往是求矩形面积并集或周长并集的好工具，当然，也可以运用在二维图中。
当然它不止可以从上往下扫，还可以从左往右扫：
（当然自己画的图可能丑一些，我解释一下，那个紫色的是扫描线）
如果说我们要求这个两个矩形的并面积怎么求？
当然你可能是啊啊\(Sonnety\)真是个笨蛋呢这我直接容斥：\(S_1+S_2-S_1\times S_2\)。
但是要是数据范围很大呢？多步容斥？你又不知道几个矩阵是不是都有交集。
这下不得不跟您谈一谈我们内存及其优秀的且很快的 \(O(nlogn)\) 算法了。
求面积并：
我们跟着例题说这个：
题目链接
【模板】扫描线
题目描述
求 \(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\) 个矩形的并集覆盖的总面积。
样例 #1
样例输入 #1
2
100 100 200 200
150 150 250 255
样例输出 #1
18000
提示
对于 \(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\)。
怎么求这两个矩形的面积并？
求三个小矩形面积相加嘛。
怎么求这三个矩形的面积？
宽是两条扫描线的之间的 \(x\) 差值，长是求边嘛。
我们把每条扫描线与矩形边重合部分的左右端点记录一下， \(y\) 轴高度记录一下就可以了：
\(S=\) 两条扫描线之间高度差\(\times\)扫描线覆盖长度
如何维护 \(x\) 长度？
选择桶来维护扫描线上的 \(x\) 是否被覆盖，显然是有很多问题的：
-
Q：如果 \(x\) 不一定是非负整数？
-
A：如果 \(x\) 是浮点数或者较大（甚至不是非负数），我们需要选择离散化，使得下标对应实际的 \(x\)。
-
Q：时间复杂度？
-
A：线段树优化。
-
Q：空间复杂度？
-
A：存储左右端点的 \(x\) 坐标。
什么什么什么，等等，线段树优化？
为什么能够线段树优化？
我们把每一条垂直于 \(x\) 轴的竖边提取出来，然后把他们延伸到 \(y\) 轴上，你看，这不就把 \(y\) 轴分割成了线段？
因此，我们设 \([1,2]\) 是我们第一个被切割出的长方形横边长度，以此类推，\([l,r]\) 就是我们需要维护的区间：
-
区间的左右端点 \(l,r\)。
-
区间被覆盖的次数。
-
区间被横边覆盖的长度。
首先，当我们遇到一个横边的时候，区间就肯定被覆盖了至少 \(1\) 次。
于是，我们统计线段树根节点的长度标记，乘两条横边之间高度差就得到了一部分的面积。
（如果到线段树就看不懂了没关系，这都有点涉及代码实现了，所以走到代码就懂了。）
那么如何求区间被横边覆盖的长度？
然后就经典线段树嘛，如果这个线段被完全覆盖直接就是右端点减去左端点，否则就只拿被覆盖的呗。
然而然而，如果我们遇到新的一条横边，之前的线段树维护的什么被覆盖的次数都是错的，必须清空信息，为了优化时间复杂度，我们选择：
将矩形的上边的和下边的赋为相反的权值。
由于我们的扫描线是从下往上走的，那么完全可以将矩形的下边赋值为 \(1\)，给矩形的上边赋值为 \(-1\)，当我们遇到下边时，说明这个矩形还会在我们分割的多个小矩形部分出现，所以它对应的区间被覆盖的次数加 \(1\)，之后统计它的影响，当我们遇到一条上边，之前一定已经统计完下边的影响，应该将对应区间的覆盖次数 \(-1\)，此时该矩形面积统计完毕。
最后我们还有一个需要解决的问题：
线段树存在长度为 \(1\) 的点，但是这个节点对应的应该是一个 \(x\) 坐标，也就是说，像这样的叶节点，却保留了两种信息。
而且我们早已确定的是，左右儿子没有交集，但是相邻的两个线段 \([1,2]\) 与 \([2,3]\) 显然存在了交集 \(2\)，我们必须考虑改变区间与横边的映射关系。
答案是将原本表示区间 \([l,r]\) 的节点表示区间 \([l,r+1]\)，这样就兼容了。