线段树:旅馆安排

发布于 2017-04-12  1.39k 次阅读


[toggle hide="yes" title="题目" color=""]

[/toggle]

实质上就是最大动态连续和。

嗯,这个代码比较渣,线段树打的很垃圾,所以常数很大,但是勉强没有超时。

大致思路就是维护三个信息:ml[o]:o节点对应区间内最长前缀所对应下标,mr[o]:o节点对应区间内最长后缀对应下标,mp[o]:o节点对应区间内最长连续区间的长度。

维护前后缀只需判断是否能跨越区间,若能跨越区间则取另一区间的值。注意:当其为0时,让l或r取到当前区间内不可能取到的位置,即可排除非法情况。

查询时,先判断根节点的长度是否大于P,若小于则直接输出0。若大于,则最长区间有3个可能的位置:1.完全处在左子树。2.夹在左右子树中间。3.完全处在右子树。因为所求的是最小下标,所以只要按上述顺序考察,满足其中一个则递归查询,最后返回的一定是最优解。

 

[toggle hide="yes" title="标程" color=""]

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974