hdu 3642 Get The Treasury (线段树+扫描线,求长方体体积交)

hdu3642题目链接

题意:给出若干个(1000)长方体,求至少交三次的空间的体积。

尺寸为[x1,x2],[y1,y2],[z1,z2],其中x,y的坐标的绝对值不超过1E6,Z的坐标的绝对值不超过1E9.

思路:

线段树+扫描线。

由于Z的坐标范围比较小,我们的做法是 利用“微分”的思想,将每个长方体,想成若干的高度为1的矩形(矩形片)

因此就转化成了求矩形至少交三次的面积

其中和矩形交,也就是矩形至少交2次的面积比较类似,只不过线段树多维护一个至少三次覆盖的长度的域。

 

假设我们有一个长为5,宽为6,高为7的长方体

那么我们就要将其拆成7个,长为5,宽为6的矩形

将所有长方体处理完之后,枚举高度,对于每一个高度,如果矩形大于等于三个,就做一个“矩形的三次面积交”操作,将答案累加。

2A,PushUp的时候写错了一句。。。即如果父亲节点已经覆盖了两次,那么父亲节点被覆盖三次的是从左右儿子被覆盖一次的情况得来的

 

 

 

hdu 1828 Picture (线段树+扫描线 求 矩形周长并)

题目链接

题意:

求矩形周长并。

思路:

线段树+扫描线。

和前面的求面积并比较类似,我们先考虑平行x轴的线段,考虑线段树,维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len.

只不过我们这次求的是每条扫描线的长度对周长的贡献,因此不需要乘高度。

 

需要注意的是,每条扫描线对周长的贡献,是目前扫描线的长度,与上一次扫描线长度的差的绝对值。(不是与上一次答案的差的绝对值!)

演示x轴求长度和的部分  图片来自 lwt聚聚的博客
这里写图片描述

以及一个小细节是,求面积的时候,最后一条扫描线对答案是没有贡献的(因为每次是求当前扫描线与下一条扫描线之间的面积)

但是求周长的时候,最后一条扫描线是一定会对答案有贡献的。

 

hdu 1255 覆盖的面积 (扫描线+线段树 求矩形面积交)

题目链接

题意:

求n(1000)个矩形的面积交,也就是至少有2个矩形覆盖的区域的面积

思路:

矩形面积并_hdu1542解题报告    类似

面积并问题中,线段树len维护的是至少覆盖一次的区域的长度

在面积交的问题中,我们需要多维护一个”至少覆盖两次的区域的长度”的域(设为double two;)

同时也要维护至少覆盖一次的区域的长度(设为double one;),是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到(好像是废话)

PushUp的时候要格外注意当前节点被完整覆盖一次的情况。

此时tree[rt].two 可以由两个子区间的one的情况想加得到

因为rt节点被完整覆盖了至少一次,那么如果rt儿子区间中被覆盖了至少一次,对于rt区间中被rt<<1和rt<<1|1覆盖至少一次的区间在对于rt区间就已经覆盖了至少2次

 

以及要注意题意说得不够清楚。最后保留2位小数是四舍五入。

读入的实际上是左下角和右上角的点。。。。

 

 

 

hdu 1542 Atlantis (线段树+扫描线求矩形面积并,模板题)

hdu1542题目链接

题意:

求n(100)个矩形的面积并。

思路:

扫描线+线段树

题目是2000年中欧区域赛的题目,虽然年代久远,但是有好几个点还是很值得学习的。

 

首先是离散化的适用范围:

之前比较常用的是将比较大的整数值离散化,常常是因为数值太大无法作为下标。

那么其实,浮点数有的时候也需要进行离散化,比如作为数组的下标,比如用来枚举。

做法上是和将较大的整数值离散化没有区别,因为遇到的题目不多,所以特意记录一下。

 

第二点是扫描线的思想:

其实扫描线的思想很早就接触过,noip2011的时候,tyvj上有一道类似的题目,不过是一唯的,当时印象深刻的是@Ocean 兄的那个比喻:

一段公路上右很多区间要收不同的费用,区间的开始给一个标记,表示该段区间对答案有贡献,区间的结束拿走该标记,表示该段区间对答案的贡献结束。

这就是扫描线的思想。

 

第三个是处理线段覆盖问题的一般做法:

通常线段树的节点处理的都是点,处理线段的时候就会比较麻烦。

  另外很重要的一点就是, 线段树都是维护一个点集, 但是对于边的问题就会变得很麻烦,  我们可以按照区间左端点建立线段树, 那么一个点表示的就不是点了, 而是起点在这个点的一个线段。  这样的话, 右区间就要相应的-1, 例如更新区间[1, 4], 就相当于更新标号为[1, 3]的线段。

这也是处理线段覆盖问题的通用方法。

对于上面引用中提到的例子中“更新[1,4],就相当于更新标号为[1,3]的线段”,是因为标号为1的节点代表区间[1,2],标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]

 

接下来具体讨论这道题目的做法:

将矩形按平行x轴方形构建扫描线(只是思想,不用实际构造),

每个矩形2条平行x轴的边分类{上边,下边}2类,如果我们从下往上“扫描”线,那么[下边]就表示了对答案贡献的开始,[下边]就表示了对答案贡献的结束。

  • 扫描线扫描的过程(建议配合代码模拟)

    以下图转载自@kk303的博客

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点13更新为1

这里写图片描述

扫到第二根线, 此时S=lcnt!=0h线, 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

 

 

 

参考资料:

HDU 1542 Atlantis(线段树:扫描线)

HDU 1542 Atlantis(线段树求矩形面积并)

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)