codeforces #381 div2 E. Alyona and towers (线段树 区间合并)

e:题意:那个数,定义hill为一段连续的区间,满足该区间为严格单峰。现在有若干操作,每个操作是对某段区间的数同时增加一个数,问每次操作后,所有的hill中,宽度最大的(区间长度最大)的是多少。

思路:同时增加一个数很线段树。。。但是要维护什么呢。。。?

猜测:肯定要维护一个区间中hill的最大宽度…

但是合并的时候要怎么办呢。。。

考虑两个方向的合并。。。

所以还要维护一个区间中,包含右端点的向左单调减延伸的长度,以及左端点的值。

同理,要维护一个区间中,包含左端点的向右单调增延伸的长度,以及右端点的值。

那么每次pushup的时候,就是两个区间hill的最大值,以及两个方向合并的最大值中取最大。。。

。。。上面是我口胡的。。。

upd:

口胡的还是有点靠谱的(并没有2333,还是漏了情况)

具体题解见代码注释

以及,为了过这道题先过了在岛老师空间题解中提到的两道题目:

hdu 3308 题目链接

hdu 5367题目链接

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz