扫描线求矩形面积并
先copy一下大佬画的图片.
三个矩形如左图所示，而若要计算面积，看右图，用3个矩形各自的面积之和减去重复部分（红色和蓝色）的面积
人算很简单，但是用算法怎么实现呢？
此类问题一般都是用线段树辅助扫描法来计算；
什么是扫描法？有什么用？怎么用？
可以想象成一根假想的线，将图从左往右或从右往左或自下而上或自上而下“扫描”一遍，至于扫描的是什么则根据具体应用选择。
扫描线可以计算矩形面积、周长，可以计算线段交点，可以实现多边形扫描转换，在图的处理方面经常用到。
这里总结一下扫描线计算矩形面积和周长的算法。
怎么用？首先，对于之前的图，除了用总面积减去重合面积，还可以换一种计算方法，如图：
此图用4条横线将整个图划分成了5个部分，显然此时再算面积就可以用各个颜色的部分求和。
想想，这样计算的整个慢过程：
假设我们的视线自下而上，首先，我们看到了最下面灰色矩形的下边，
用这个下边的长度乘以这条边和上一条边的高度差即得到灰色矩形面积，
继续看到蓝色的矩形的下边，虽然蓝色矩形有两个，但我们计算时自然会用结合律将两个矩形的下边加起来再去乘以同样的高，
然后重复这样的操作，我们最终可以求得整个图形的面积。
首先的问题是，计算机要怎么保存这张图这些矩形？
从刚才的过程，我们不难发现，我们只需要保存这张图里面的所有水平的边即可。
对于每条边，它所拥有的属性是：这条边的左右端点（的横坐标），这条边的高度（纵坐标），这条边属于矩形的上边还是下边（想想为什么保存这个属性）
刚刚计算中我们遇到两个蓝色矩形的一部分一眼就能看出这两个蓝色矩形的‘宽’是多少，用计算机怎么做到？
线段树华丽登场!
我们以整个图最左边的竖线作为区间左端点，最右边的竖线作为区间右端点，去维护这个区间的有效长度（即被覆盖的长度）
比如扫到第2条边的时候，有效长度就是两个蓝色矩形的宽之和。
这样，我们用扫描线去扫描每一条边的时候，都需要更新线段树的有效长度
是如何更新的呢？
如果扫到的这条边是某矩形的下边，则往区间插入这条线段
如果扫到的这条边是某矩形的上边，则往区间删除这条线段
为什么？自己试着模拟一下就不难发现：
因为我们是自下而上的扫这个图，扫到下边相当于刚刚进入一个矩形，扫到上边则是要离开一个矩形
利用线段树把每条边的有效长度找到了，也就是找到了每部分的所有矩形的总宽，那么高呢？
高就简单多了，对于所有的边，按照高度从小到大排列，那么矩形高就是每相邻边之间的高度差
简单来说：扫描线就是将总面积分块来求，只不过分块的方式有些精妙，利用线段树来维护当前部分面积的长（或宽）。
参考博客：https://blog.csdn.net/tomorrowtodie/article/details/52048323