面积并扫描线
前言
模板题:P5490 【模板】扫描线
这是一道经典的题目,需要求出
扫描线算法的基本思想就是用一条线从下往上扫过图形,计算出相邻两条横边之间的面积,然后求和即可。扫描线的过程中需要知道相邻两个横边之间的距离,以及这当前位置图形的宽度。我们只需要将横边排序就可以知道相邻两个横边之间的距离,而当前位置图形的宽度可以用线段树来维护。
线段树
线段树需要求出当前位置图形的宽度,我们要如何修改当前位置图形的宽度呢?我们看下图:
(图片来自网络)
我们可以发现,扫过一个矩形的下边就会增加图形的宽度,而遇到一个图形的上边就会减少图形的宽度。我们可以拿括号序列来举例:如果一个位置前面的左括号个数等于右括号个数,那么这个位置就不在任何括号中。同理:如果一个位置扫过的矩形下边个数等于矩形上边个数,那么这个位置当前没有被图形覆盖,反之则被图形覆盖。我们只需要记录一个位置当前已扫过的矩形下边个数减去已扫过的矩形上边个数,我们就可以通过这个数是否为
现在我们要记录一条横线上的每个位置的值,并且我们每次需要求出有多少个值不为
不过我们需要维护的是两个相邻
这样我们就可以写出线段树了。
1 | void pushup(int x) |
排序
在扫描线算法中,我们总共需要两次排序:将端点的横坐标排序和横线的纵坐标排序。在进行排序之后,我们还需要将端点横坐标离散化和去重,用 STL 的 unique 函数就可以了。
1 | struct str |
扫描线
有了上面的所有准备,我们就可以写出扫描线了。我们只需要从第
1 | build(1,1,m-1); |
code
1 | #include<cstdio> |