Hades18 @ 2018-10-30 20:43:44
我们考虑维护每一个块前缀最大子段和,后缀最大子段和,块内最大子段和.
由于
我们将每一个块合并成正负相间的点,相邻整点合并后贡献会减小.
此时考虑这个块合并的点的个数是单调的,每次修改只能使点减少,所以维护均摊
最后块与块之间像线段树维护最大子段和一样的合并就好了.
(所以复杂度有没有算错啊,没有我就写了...)
@noip ???
by noip @ 2018-10-30 22:13:57
这题AC的除了我都是这种做法吧
不过局限性是只能加正数，而且复杂度目前这个做法只能达到nsqrt(nlogn)
by Hades18 @ 2018-10-31 06:56:37
我发现哪里胡挂了，还是老老实实去打带log的吧
by noip @ 2018-10-31 22:06:57
@Hades18 luogu上带log跑的挺快，不过bzoj上就不行了，应该是内存访问速度的问题
by noip @ 2018-10-31 22:07:34
这题带log难度就降了至少2-3级吧
by Happynewyear @ 2019-04-20 15:31:26
考古
by __zyy_wgcs__ @ 2023-08-15 15:43:54
考古