本文共 3546 字,大约阅读时间需要 11 分钟。
三个月以来的第一题。。。
这道题是二维的线段树,需要转化为一维。
首先只考虑x轴,将每个点看成两条线,入线和出线。入线的x坐标是点的x坐标,亮度是点的亮度;出线x坐标是x+W, 亮度是点的亮度的负值,即-c。这样做的原因是如果我们按照x的大小从左往右处理所有的点(想象一个以每个点再左下那么一点点为左下角的矩形扫描,左下那么一点点是为了包括点),入线表示我们到了点的作用范围,出线会取消掉点的作用。为了能这样从左往右处理,我们需要把所有的入线出线按照x坐标从小到大排序。x值相同的时候,亮度为负值的点需要先处理,这样保证我们不会多算亮度和(即避免有个点已经不起作用了,仍然暂时算进去了)。
然后考虑y轴,由于上述处理方式,我们已经能够保证每个在线段树里面的点x是在作用范围内的,所以我们只用在处理每个点的时候把点加入到其y轴作用范围内就好了,即[y, y + H - 1]。这个范围是由于我们上述描述的矩形的位置决定的。
由于y值范围可能很大,为了减少线段树的空间消耗,我们可以将y离散化,即把所有y, y + H - 1排序,给个编号。编号仍然能表示两个y值的大小关系,但大大减少了数值范围。
我的线段树实现一如既往的慢。
| | Accepted | 3216K | 547MS | | 3282B |
/* ID: thestor1 LANG: C++ TASK: poj2482 */#include #include #include #include #include #include #include #include #include #include #include
转载地址:http://hvxli.baihongyu.com/