求问：玄关

学术版

Genius_Star @ 2024-06-09 21:54:36

两个序列a,b，支持a，b区间加，求区间max ai*bi

可做吗，可做给一下做法，谢谢。

by Frank_08 @ 2024-06-09 21:57:19

@Genius_Star 这不是ABC的F吗？应该是分块吧。

by 解方橙 @ 2024-06-09 22:03:47

@Genius_Star

\Sigma\ (a_i+x)b_i=\Sigma\ a_ib_i\ +x\Sigma\ b_i

lazy segtree维护suma，sumb，ans即可，一个log

by _O_v_O_ @ 2024-06-09 22:05:03

@解方橙 @Saint_ying_xtf 你说得对，但这是区间max不是区间和吧

by Frank_08 @ 2024-06-09 22:10:07

@_O_vO 哦哦不好意思看错了

by Mikefeng @ 2024-06-09 22:19:39

分块吧，整块维护凸壳二分斜率，散块暴力重构，根号log。

by Mikefeng @ 2024-06-09 22:20:04

不知道KTT能不能做。

|