题解

思路

若当前还能吸收某个相邻史莱姆，立刻吸收不会使最优答案变差。

做法

设高桥当前已经覆盖区间 $[l,r]$，大小为该区间元素和 $sum$；找到左侧最近的 $A_i\ge sum$ 和右侧最近的 $A_j\ge sum$，那么两者之间除高桥所在区间外的所有元素都严格小于当前大小，可以整批吸收，随后用前缀和更新 $sum$。若区间不再扩大便得到该起点的答案。

每次成功扩张至少会使高桥的大小翻倍，因此单个起点至多扩张 $O(\log\sum A)$ 轮。

复杂度

用维护区间最大值的线段树在 $O(\log N)$ 时间内找两侧最近的不小于给定值的位置，总时间复杂度为 $O(N\log N\log\sum A)$，空间复杂度为 $O(N)$。