vijos1083

题目链接

线段树练习_vijos1083

题解

拿到线段树的题都很膨胀啊….

两分钟维护区间最大值+单点修改+区间查询+过样例=WA0….

我也是心情复杂…

结果看到题目中说到一个

只包含一个整数,表示 小白可以选出的公园得分和的最大值 .

得分和啊…

瞬间想好一个\(O(NlogN))\)的暴力有屁用….


仔细思考可以发现对于一个区间的最大 连续子段和而言,我们可以额外开三个标记维护一下,\(lmax\)表示的是左端点开始的最大和,\(rmax\)表示右端点开始的最大连续子段和,\(amx\)表示的是区间最大,\(tr\)表示的是区间和.有点像动态规划???

因为修改可以改成负数的啊….

所以维护的时候..

上面的推导标记移动的时候,最好还是拿手推一下的好,大意还是指父亲节点的值由左右儿子节点总结而来.只不过转移的方式有些许的变化,感觉这道题可以放到动态规划里面水一水.

是不是说我水了一道用线段树优化动态规划的题,woc牛逼

23333…

其他都是单纯的区间查询+单点修改喽..


By:Wahacer

2017.12.18

11:35

发表评论

电子邮件地址不会被公开。 必填项已用*标注