关于最大字段积

ningago @ 2022-04-02 10:16:58

by 约瑟夫用脑玩 @ 2022-04-02 10:20:14

斗胆猜测一下可能的答案区间只有 O(1) 个，只与负数个数和最靠左和最靠右的负数有关。

有 0 或者有小数就当我没说。

by 约瑟夫用脑玩 @ 2022-04-02 10:23:21

有 0 其实没啥问题，主要是有小数就真的要用线段树了。

大概就是小学就知道的加法和 0 比较，乘法和 1 比较，然后乘法分个正负，就是纯细节。

by donghanwen1225 @ 2022-04-02 10:23:31

大概要维护最大、最小前缀积和最大、最小后缀积，然后合并区间时考虑最小前缀后缀积和最大前缀后缀积应该就可以了

另外还要注意比如如果某个区间的积是负数，合并最小前缀后缀积的时候要和最大前缀后缀积乘起来之类的细节

by 约瑟夫用脑玩 @ 2022-04-02 10:27:34

这题出诈骗还好，真出线段树会掉精度吧。

by optimize_2 @ 2022-04-02 10:44:39

我口胡一下 全部取 log 然后最大字段和

by 约瑟夫用脑玩 @ 2022-04-02 10:48:11

@optimize_2 有负数，不清楚有没有 0。

by violetctl39 @ 2022-04-02 10:49:04

@ningago 不带修就和这题差不多CF1660D。显然若干个 0 可以把序列分开，每一段可以单独维护。带修的话，可以 set 维护，每个段内维护负数的位置。记 s_i 是第 i 段的乘积，pre_i 是第 i 个数的前缀积，suf_i 是后缀积，那这一段的答案就是 s_i 除以第一个负数的前缀积，或除以最后一个数的后缀积。答案就是每一段的答案最大值。前缀后缀可以线段树或树状数组维护。（也许是我在口胡

by violetctl39 @ 2022-04-02 10:51:17

若 s_i 就是正的就不用除以负数的前后缀积了。

by FunnyCreatress @ 2022-04-02 10:52:48

没小数随便乱杀，有小数要分别维护正负的绝对值最大子段积信息，如果要取模还要维护绝对值的对数的最大子段和信息，好像巨大难写

by 约瑟夫用脑玩 @ 2022-04-02 11:00:49

维护小数信息（对数）什么的真的不会掉精度吗。