@[paulzrm](/user/226760) 前缀和之后有，$\min + $ 卷积归约
by Alex_Wei @ 2022-11-25 17:28:44
最好 $n ^ 2$
by Alex_Wei @ 2022-11-25 17:29:05
$O(n^2)$。首先显然第一个问题可以全体加极大数变成第二个问题，所以这两个问题没有区别。然后这又可以规约成一般的 $(\max,+)$ 卷积，这目前并没有什么优秀做法。
如果仅仅是要求凸包的话是可以分治+闵科夫斯基和做到 $O(n\log n)$ 的。
by FunnyCreatress @ 2022-11-25 17:33:18
怕不是[这道](https://uoj.ac/problem/245)哟，这道能出出来说明没什么更优秀的做法。
by bai_tang @ 2022-11-25 18:11:35