zcmimi's blog

arrow_back凸包共1篇文章

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

  1. 区间加
  2. 求序列最大前缀和

区间加,相当于前缀和加上一个等差数列

而等差数列加上一个等差数列还是等差数列

考虑将每个位置的前缀和转化为一个一次函数kx+b

分块,对每个块维护一个上凸壳单调栈,可以二分找到最大值

1/1
Search
search