单调队列优化DP的好题

单调队列优化DP是一种常用的优化方法，可以将时间复杂度从 $O(n^2)$ 降低到 $O(n)$ 或者 $O(n \log n)$。以下是一道利用单调队列优化DP的典型题目：

题目描述：

给定一个长度为 $n$ 的序列 $a_i$，定义 $f(i)$ 为 $a_i$ 到 $a_n$ 中的最小值，即 $f(i) = \min\limits_{j=i}^n a_j$。现在定义 $g(i)$ 为满足 $f(j) \ge a_i$ 的最小下标 $j$，即 $g(i) = \min\{j \mid j > i, f(j) \ge a_i\}$。如果不存在这样的下标 $j$，则 $g(i) = n+1$。

现在请你计算出 $1 \le i \le n$ 的所有 $g(i)$ 的值。

输入格式：

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式：

输出 $n$ 行，第 $i$ 行输出 $g(i)$ 的值。

输入样例：

5
3 1 2 4 5

输出样例：

2
5
5
5
6

解题思路：

设 $dp(i)$ 表示 $g(i)$，那么 $dp(i)$ 与 $dp(i+1)$ 的转移关系可以表示为：

$$dp(i)=\begin{cases}i+1, &\text{if}\ f(i+1)\ge a_i \\dp(i+1), &\text{else}\end{cases}$$

这个转移方程可以使用暴力 DP 解决，时间复杂度为 $O(n^2)$。但是，我们可以使用单调队列优化 DP，将时间复杂度降为 $O(n)$。

我们定义一个单调队列 $q$，存储下标。队列 $q$ 中的元素满足：

- 队列中的元素是单调递减的，即 $q_1 < q_2 < \cdots < q_k$；
- 对于任意的 $i\in [1,k]$，有 $f(q_i) \ge f(q_{i+1})$。

队列 $q$ 的作用是维护一个长度为 $k$ 的区间 $[i+1,q_k]$，满足这个区间中的所有 $j$ 都满足 $f(j) < f(i+1)$。

根据定义，当我们要求 $dp(i)$ 时，只需要查找队列 $q$ 中第一个满足 $f(q_j) \ge a_i$ 的位置 $q_j$，那么 $g(i) = q_j$，如果队列 $q$ 中不存在这样的位置，则 $g(i) = n+1$。

那么如何维护单调队列 $q$ 呢？我们可以在每次 DP 的过程中，将 $i$ 加入队尾。然后判断队首元素 $q_1$ 是否满足 $f(q_1) \ge a_i$，如果满足则弹出队首元素，直到队首元素不满足条件为止。

由于每个元素最多被加入队列一次，并且最多被弹出一次，因此时间复杂度为 $O(n)$。具体实现细节可以参考下面的代码实现：