本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-28 10:51:42

单调队列适合这样的转移方程：

$$ f(i) = \min\limits_{L_i \le j \le R_i} \{f(j) + a_j\} + b_i \space \text{s.t.} \space L_t \lt L_{t + 1}, R_t \lt R_{t + 1} $$

如果我们使用朴素的方法求解这个方程，时间复杂度大约是 $O(n^2)$ 的（实际上是 $O(\delta n)$，其中 $\delta$ 是每一个区间的宽度）。这是因为对每一个点 $i$，我们都需要遍历一个区间内的 $j$ 并且取其最值。

我们发现，对不同的 $i$，我们计算的 $j$ 是有重叠的；并且，由于这些计算出的结果并不依赖 $i$，因此我们可以使用单调队列的方法，保存重叠的 $j$ 区间中 $f(j) + a_j$ 的最大值。

这样，在计算 $f(i)$ 的时候，我们只需要在单调队列中加入找到在这个区间内的最大值即可。由于这些区间都是递增的，因此超出了某个点 $i$ 的点 $j$，我们可以直接将其从队列中删除。

这样实际复杂度达到 $O(n)$