hit oj 2687 Candy (线段树动态维护最大连续子段)

题目链接

题意:给出n个数,m个修改,每次修改后询问整个区间的最大连续子段。

思路:考虑一段区间,分成左右两个子区间,这段区间的最大子段有三种情况:只在左区间中,只在右区间中,既在左区间中又在右区间中。前两种很好维护,对于后一种,我们新增加线段树的两个域,mxl,mxr,分别表示一个区间中包含左端点在的最大字段和(也就是最大前缀和),和一个区间中包含右端点在的最大子段和(也就是最大后缀和),然后对于最大子段既在左区间又在右区间的情况,只需要合并【左区间的最大后缀和 】和【右区间的最大前缀和】就好。

关于一个区间最大前缀和的维护,取该区间的左区间的最大前缀和和【该区间的左区间和】+【该区间的右区间的最大前缀和】的最大值。

最大后缀和同理。

这是一种很经典的做法,注意体会。

1A

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz