[POJ 2482]

Stars in Your Window

这题前面竟然是一封情信,字里行间都饱含作者的深情……于是又搜了下kinfkong,是位中大的前辈哦,都31岁结婚了。他博客里的文章也挺有意思的……

扯远了,回到题目本身吧。题面是:在二维平面上有N颗星星,各有一个亮度值c,问如果用一个长W宽H的矩形来括住某些星星,如何使窗口内星星亮度和最大。

说实在的,题目本身也出得非常巧妙。解题需要两次利用区间值求和的思想,即在[a,b]区间上加c,相当于在顺序遍历的基础上在a点加c,b+1点减c。第一次是在y轴方向上,若在(x,y)点处有一颗星星亮度为c,则在(x,y+H)上增加一颗亮度为-c的星星。这样,由y=0向上更新线段亮度值,便能将矩形区域求最大和转换成线段求最大和。第二次则是在x轴方向上的,对横坐标x亮度为c的星星,增加一颗x+W处亮度为-c的星星,这样便能进一步将线段最大和转换成点最大值。由此,便能利用线段树在每次插入星星的同时O(lgN)地更新最大亮度值了。

不过题目分类里写得这题属于“静态二叉检索树”。。。。这个暂时还没想出来该怎么写。。。