题解：P14475 大鱼吃小鱼

题目中 $\{a_i\}$ 表示鱼的体型，$n$ 表示总数。

首先，任何时候鱼的状态一定是“吃完了一个区间位置中的所有鱼”。并且鱼的体型一定等于区间内鱼的初始体型之和。所以我们用这个区间来表示鱼的状态。以下，将区间内的鱼的体型之和简称为区间和。

我们称：

显然，小鱼区间是不可能不用道具去吃任何鱼的（因为鱼的体型都非负）。

我们考虑任何一个鱼从初始吃完所有鱼的过程。这个过程中鱼的体型显然是单调不降的，存在一个时刻第一次变成大鱼，在这之前必然每一步吃鱼都要用道具。（或者可能整个序列都是小鱼，这种情况下答案为 $n-1$。这种情况要特判。）我们从这个时刻把一个方案分成前后两段：

如果两个自闭区间相交但互不包含，可以证明它们的交集部分一定是小鱼区间。（否则，我们设它们按位置顺序是 $A-b-C-d-E$，其中 $b,d$ 是单条鱼，$A,E$ 可以为空，$C$ 不为空，两个自闭区间分别是 $A-b-C$ 和 $C-d-E$。则，按自闭的定义有 $d \gt A+b+C-k, b\gt C+d+E-k$。如果 $C \ge k$ 就有 $d\gt A+b \ge b \gt d+E \ge d$，矛盾。）

另外，容易证明一个自闭的大鱼区间下一步用道具吃的一定是两侧相邻的鱼中体型较大的，因为吃了较大的那个后体型一定足够立刻吃较小的，这总是更优。

所以对于一个大鱼区间，所有包含它的自闭区间必然组成区间套，并且方案选择是固定的。

另外，这也容易证明大鱼自闭区间的总数不超过 $2n$ 个。我们考虑把一个大鱼自闭区间关联到它两侧相邻的鱼中较小的那个上，容易证明每个鱼在每一侧最多会被一个大鱼自闭区间关联。（$a-B-c-D$，容易证明不可能有 $B$ 和 $B-c-D$ 都是大鱼自闭区间且有 $a\le c$。否则 $B+c+D\ge B+a+D \gt B+(B+c+D-k)+D \ge B+(k+c+D-k)+D = B+c+2D$，矛盾）

现在问题有两个：

对于第一个问题，我们考虑分别对于每个位置求出每一侧与他相关联的那个大鱼自闭区间（若存在）。我们考虑从左往右枚举 $i$，并用双指针维护以 $i-1$ 为右端点的极短大鱼区间记为 $[L_{i-1},i-1]$，并在 $i$ 增加过程中维护 $L_{i-1}-1$ 左侧所有的点集 $S$ 中可能成为左相邻点的，试图求出以 $i-1$ 为右端点且关联到 $i$ 的大鱼自闭区间。那么：

从左到右、从右到左分别做一遍这个过程就解决了第一个问题。

对于第二个问题，我们不妨设 $f([l,r])$ 表示区间 $[l,r]$ 的答案。显然有 $f([1,n])=0$。然后对于一个大鱼自闭区间 $[l,r]$，按前文有 $f([l,r])=f(M([l-1,r]))+1$（当 $a_{l-1}\ge a_{r+1}$）或者 $f([l,r])=f(M([l,r+1]))+1$（当 $a_{l-1}\lt a_{r+1}$），其中 $M$ 表示包含这个区间的最小自闭区间。（按前文引理，包含一个大鱼区间的最小自闭区间是唯一的。）

所以我们只要查询出所有这些 $M$ 然后递推计算就行了。用扫描线+单调栈处理一遍所有大鱼自闭区间即可求出所有需要的 $M$。

前面所有步骤都是 $O(n)$，所以这个问题的时间复杂度是 $O(n)$。