扫描线套路：

从每个矩形的竖边，都做一条垂直的线

画完竖线之后统计面积

统计面积的方法：以每个柱形区域为单位来统计，如下图，每个颜色代表一个柱形区域



每个柱形区域的面积就是这个长条的宽度××阴影部分高度

宽度就是柱形两边竖线的横坐标之差，设右边竖线横坐标为xjxj，左边竖线横坐标为xixi，则宽度为xj−xixj−xi

下图用x1,x2…x6x1,x2…x6表示横坐标



这样巧妙地用阴影部分的高度就解决了多个矩形相互覆盖的问题。



那么现在的问题就变成了：如何快速统计出来每个区间内部阴影部分的高度hh ？

这就需要用到一个非常特殊的线段树了，之所以称之为“非常特殊”是因为这个做法比较难扩展，只适用于这一类题型。



线段树中的每个结点struct Node除了存储左右边间l, r，

还要存储一个cnt,表示当前区间被覆盖的次数，

还有一个len，表示至少被覆盖一次的区间的总长度。

另外，扫描线题型会用到懒标记延迟更新的思想，然后这类题型特殊的地方就是它的懒标记不更新，即不往下传（懒标记是pushdown操作，用父结点的信息更新子节点的信息）。



那么我们现在再看一下它的每个标记真实的含义是什么，以及它的每个子节点的信息有什么特点。

cnt、len标记存的是在不考虑父结点信息情况下的结果。

这两个标记不考虑上面的父结点信息，只考虑下面的子节点信息，这就是扫描线的特殊之处。





操作步骤：



首先把每个矩形的左右两个边拿出来，变成一个三元组。（线段树维护的是纵坐标，把每个矩形的竖边看成一个带权值的线段）



第一个操作是给[y1,y2]+1[y1,y2]+1,表示这个矩形已经过来了（想象一下，竖线是扫描线，固定不动，一个个矩形从右向左飘过来）



第二个操作是给[y1,y2]−1[y1,y2]−1，表示这个矩形已经全部穿过扫描线离开了。







有了这两个操作后，我们每次想统计两个相邻竖边内被阴影部分覆盖的总高度怎么办呢？

这个高度其实就是根结点的len的值。

说的再详细一点，我们规定，每个矩形的左竖边权值为+1，右竖边权值为-1，每次经过扫描线时，扫描线上的cnt会加上或减去经过它的矩形的竖边的权值，所以在算每两个竖线之间阴影部分面积时，阴影部分的高度就是扫描线上此时的len，而扫描线上的len其实就是根结点的len，我们只算扫描线cnt大于0的时候的情况（实际上扫描线也不存在cnt为负的情况，因为每次cnt减1的时候之前已经必然加过1，当所有矩形都离开扫描线后，扫描线cnt一定为0，所以扫描线只有cnt为大于0和等于0的情况），也即，只有在扫描线上的cnt大于0，说明这段区间上有阴影部分，我们才会继续计算。



小细节：线段树在本题中维护的是一段区间，这就需要把结点与区间对应起来

例如，结点y1y1对应的区间为[y1,y2−1][y1,y2−1]







完整链接：https://www.acwing.com/solution/content/65301/

20软四李杨帆