线段树进阶----扫描线求 面积并&周长并

一．扫描线
　　简而言之，就是将每个矩阵拆成两条平行的线段（以平行于y轴的线段为例，记录它的x轴坐标，以及它在y轴上所代表的区间），按x轴排序后再一路扫过去（线段与线段之间即为若干个可求解的矩形，依次计算即可），同时，再利用线段树维护y轴上的区间（算是优化吧）。
　　详细的网上都有，故不详讲（其实比较容易理解）
　　贴个blog吧

二．离散化相关
　　好吧，这是我认为的应该注意的地方　　谁让我被坑了若干遍QAQ
　　离散化好说，直接sort、unique、lower_bound三步走，这里主要是离散化后对应的区间。
　　给定一个处理好了的数组
　　　　num[]={0, 5 , 7 , 9，15，53，79，153，254，523，721}
　　　　（离散化后的值对应该元素在数组中的位置）
　　１.由于是左闭右开区间，因此建立［１，９］的线段树即可
　　２.对于线段树所管理的区间［ｌ，ｒ］/［ｌ，ｒ + 1），它实际代表的区间就是［num[ｌ]，num[ｒ + 1]）
　　3.对于修改区间［ｌ，ｒ），若ｌ＝＝ｒ，则无视掉

三．面积并
　　扫描线的那部分就不讲了，主要讲讲线段树
　　对于y轴上的一段区间，需要记录
　　　　len:区间内被覆盖的长度
　　　　cnt:整个区间被覆盖的次数
　　由于所有修改之后，cnt的值必定为0，对于区间的修改，可以不考虑下放标记。则：
　　1. cnt＞０　　　len＝区间长度，否则转2
　　2. 为叶子节点 　 len＝0 　　　，否则转3
　　3.不为叶子节点　 len＝左右孩子len之和
　　
　　例题：洛谷P2061城市的地平线 　　my code
　　

四．周长并
　　一个较为暴力的办法，两次扫描线，从左往右，从下往上各一次。
　　当然，一次也是可以的。但要多记录些东西来判断线段数量（将上文的具体见上文的blog）
　　　cov：表示区间内有多少条独立的线段
　　　covl：区间左端是否被覆盖
　　　covr：区间右端是否被覆盖
　　顺便补充一个细节：
　　　线段排序时，若x轴相等，则入边优先
　　　给出一组数据

2
0 0 4 4
4 0 8 4

　　若直接按x轴判断，在x==4时，由于先加出边，再加入边，导致原本应该不能算的边算了两次（正确答案：24）
　　
　　例题：洛谷P1856 Picture　　my code

后排给广告君

最后

以上就是昏睡早晨为你收集整理的线段树进阶----扫描线求 面积并&周长并的全部内容，希望文章能够帮你解决线段树进阶----扫描线求 面积并&周长并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。