@[_FJqwq](/user/755947) n怎么说
by BGM114514 @ 2024-04-27 17:38:28
@[_FJqwq](/user/755947) 考虑扫描线，我们扫描区间右端点，动态维护左端点以及区间最值。
当右端点右移一位的时候，对一个长度为 $len$ 的区间的贡献为 $len\cdot a_r$，放到左端点上来说，就是对左边的区间加上一个等差数列。
现在问题转化为，区间加等差数列，区间最值问题。然后这个可以用一些科技比如 $KTT$ 什么的做到两只 $\log$。不过我不会，丢个 [《浅谈函数最值的动态维护》阅读随笔](https://www.cnblogs.com/joke3579/p/paperessay221202.html)
by Reunite @ 2024-04-27 17:50:43
@[Reunite](/user/377760) 右移右端点 $r$ 时，对于左端点 $l$，你没有考虑对 $[l,r)$ 的贡献吧？
by wukaichen888 @ 2024-04-27 17:56:03
@[BGM114514](/user/705058) 希望得到尽量优的做法，显然有 $O(n^2)$ 做法（
by _FJqwq @ 2024-04-27 17:57:37
@[_FJqwq](/user/755947) 直觉告诉我此题有log做法。。。
by BGM114514 @ 2024-04-27 18:10:11
@[Reunite](/user/377760) 对于一个区间的贡献还有这个区间原来这些数的值，随着len增大他们本身不也得多加一次吗。
by 聊机 @ 2024-04-27 18:52:37
抱歉，你们说的对，我没仔细想。
by Reunite @ 2024-04-27 21:52:26