单调栈和单调队列是两种常用的数据结构，它们体现了利用"单调性"来优化算法和去除冗余状态的思想。其中，单调队列优化动态规划（DP）是竞赛中常见的考点。

单调栈

Luogu P5788 【模板】单调栈

题目描述

给定一个长度为 $n$ 的序列 $a$。定义 $f_i = \min \{ j \mid i < j \leq n \text{ 且 } a_j > a_i \}$。如果不存在满足条件的 $j$，则 $f_i = 0$。对于所有 $i = 1, 2, \ldots, n$，求出 $f_i$。其中，$1 \leq n \leq 3 \times 10^6$。

题解

本题要求对于序列中的每个元素 $a_i$，找到其右边第一个比它大的元素 $a_j$ 的下标 $j$。暴力解法的时间复杂度为 $O(n^2)$，其中会遍历许多"无用"的 $j$（决策点）。如果存在两个决策点 $i$ 和 $j$，其中 $i < j$ 且 $a_i > a_j$，那么 $j$ 对于 $i$ 来说就成了无用的决策点。

我们考虑从右向左（倒序）遍历序列。每次计算完 $f_i$ 后，将 $a_i$ 加入决策集合。这样做可以保证新加入的下标 $j$ 总是小于已在集合中的下标。考虑决策集合中，除了当前元素 $a_i$ 外，最靠左的决策点下标为 $j'$。如果 $a_i > a_{j'}$，那么 $j'$ 就是无用的决策点，可以被移除。在加入新元素并移除冗余决策后，决策集合中的元素（及其下标）将满足单调性：下标递减，对应值递增。我们使用一个栈来维护这个决策集合。每次查询时，栈顶元素（的下标）就是 $f_i$ 的候选；然后，不断弹出栈顶元素，直到栈顶元素的值小于 $a_i$。这个维护决策集合的栈即为"单调栈"。

每个下标最多进出栈一次，因此整体时间复杂度为 $O(n)$。

代码示例

#include <iostream>
#include <vector>
#include <stack>

const int MAXN = 3e6 + 5;
int n;
int a[MAXN];
int ans[MAXN];
std::stack<int> s; // 存储下标

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        // 当栈不为空且栈顶元素对应的值小于当前元素时，
        // 说明栈顶元素找到了右边第一个更大的元素
        while (!s.empty() && a[s.top()] < a[i]) {
            ans[s.top()] = i;
            s.pop();
        }
        s.push(i); // 将当前元素的下标压入栈
    }

    for (int i = 1; i <= n; ++i) {
        std::cout << ans[i] << (&quot; &quot;:&quot;\n&quot;)[i == n];
    }

    return 0;
}
    

Luogu P6503 \[COCI2010-2011#3\] DIFERENCIJA

题目描述

给定一个长度为 $n$ 的序列 $a$。计算：

$$ \sum_{i=1}^{n} \sum_{j=i}^{n} \left(\max_{k=i}^j\{a_k\}-\min_{k=i}^j \{a_k\}\right) $$

其中，$2 \leq n \leq 3 \times 10^5$。

题解

将原式拆分为两部分：

$$ \sum_{i=1}^{n}\sum_{j=i}^{n}\max_{k=i}^j\{a_k\} - \sum_{i=1}^{n}\sum_{j=i}^{n}\min_{k=i}^j\{a_k\} $$

我们以计算最大值的部分为例。考虑贡献拆分：对于序列中的每个元素 $a_i$，计算有多少个包含 $a_i$ 的区间，且 $a_i$ 是该区间的严格最大值。可以通过向左和向右扩展，找到 $a_i$ 左边第一个不小于 $a_i$ 的元素（下标为 $l$）和右边第一个不小于 $a_i$ 的元素（下标为 $r$）。那么，以 $a_i$ 为最大值的区间数量为 $(i-l)(r-i)$。 $l$ 和 $r$ 可以通过单调栈在 $O(n)$ 时间内求出。枚举每个 $a_i$ 并累加贡献，总时间复杂度为 $O(n)$。

在具体实现时，需要注意单调栈弹栈条件是否包含等号。

单调队列

Luogu P1886 滑动窗口 /【模板】单调队列

题目描述

给出长度为 $n$ 的序列 $a$ 和窗口长度 $k$。对于所有 $1 \leq i \leq n-k+1$，分别求出区间 $[i, i+k-1]$ 的最大值和最小值。其中，$1 \leq k \leq n \leq 1 \times 10^6$。

题解

以求解区间最大值为例。观察单调栈的性质：在一个单调递减的栈中，栈底元素对应的值是栈内元素的最大值。对于滑动窗口问题，当窗口向右滑动时，一些元素会移出窗口。我们可以维护一个双端队列，它不仅保持单调性（例如，队内元素对应值单调递减），还会从队头（对应栈底）移除超出窗口范围的元素。

具体地，当处理到元素 $a_i$ 时：

1. 从队尾移除所有对应值小于 $a_i$ 的元素，然后将 $i$ 加入队尾。
2. 从队头移除所有下标小于 $i-k+1$ 的元素。
3. 此时，队头元素对应的下标 $q[\text{head}]$ 即为当前窗口 $[i-k+1, i]$ 的最大值。

这个过程的时间复杂度是 $O(n)$。单调队列可以看作是单调栈在处理前缀信息时的推广，特别地，单调栈可以看作是始终维护一个"前缀"的单调队列。

代码示例

#include <iostream>
#include <vector>
#include <deque>

const int MAXN = 1e6 + 5;
int n, k;
int a[MAXN];
int q[MAXN]; // 存储下标
int head, tail; // 双端队列的头尾指针

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    // 求最大值
    head = 1; tail = 0;
    for (int i = 1; i <= n; ++i) {
        // 保持队内元素值单调递减
        while (head <= tail && a[q[tail]] <= a[i]) { // 注意这里等于号，可以使得更靠后的相同值被保留
            tail--;
        }
        q[++tail] = i;
        // 移除队头超出窗口的元素
        while (head <= tail && q[head] <= i - k) {
            head++;
        }
        // 当窗口形成时，输出队头元素（当前窗口的最大值）
        if (i >= k) {
            std::cout << a[q[head]] << " ";
        }
    }
    std::cout << "\n&quot;;

    // 求最小值
    head = 1; tail = 0;
    for (int i = 1; i <= n; ++i) {
        // 保持队内元素值单调递增
        while (head <= tail && a[q[tail]] >= a[i]) { // 注意这里等于号，可以使得更靠后的相同值被保留
            tail--;
        }
        q[++tail] = i;
        // 移除队头超出窗口的元素
        while (head <= tail && q[head] <= i - k) {
            head++;
        }
        // 当窗口形成时，输出队头元素（当前窗口的最小值）
        if (i >= k) {
            std::cout << a[q[head]] << (&quot; &quot;:&quot;\n&quot;)[i == n];
        }
    }

    return 0;
}
    

Luogu U482536 环形数组最大子段和

题目描述

求一个长度为 $n$ 的环形序列 $a$ 的最大子段和。其中，$1 \leq n \leq 10^7$。

题解

解决环形数组问题的一个经典方法是"断环成链"。将序列 $a$ 复制一份接到末尾，形成长度为 $2n$ 的序列 $a'$。原问题转化为在 $a'$ 上寻找一个长度不超过 $n$ 的最大子段和。

计算前缀和 $s$。枚举子段的右端点 $i$，我们需要找到左端点 $j$（满足 $i-n \leq j < i$），使得 $s_i - s_j$ 最大。这等价于 $s_i - \max_{j=\max(0, i-n)}^{i-1} \{s_j\}$。这里的 $\max_{j=\max(0, i-n)}^{i-1} \{s_j\}$ 是一个滑动窗口最大值问题，可以用单调队列在 $O(n)$ 时间内解决。

另一种思路是考虑环形最大子段和的两种情况：一是不跨越首尾连接处，二是跨越首尾连接处。第一种情况是普通的最大子段和，可以用 Kadane 算法解决。第二种情况，即跨越首尾连接处，意味着子段之外的部分（不跨越首尾）构成了一个连续子段。由于原问题要求最大化子段和，那么不跨越首尾的子段和一定是最小的。因此，跨越首尾的最大子段和等于总和减去不跨越首尾的最小子段和。分别计算这两种情况的最大值，取较大者即可。

单调队列优化 DP

单调队列优化 DP 的本质是利用决策的单调性来排除冗余状态，从而优化 DP 转移。

Luogu P2627 \[USACO11OPEN\] Mowing the Lawn G

题目描述

给定一个长度为 $n$ 的序列 $a$。可以选择序列中的若干个数，但要求选出的数中不存在长度超过 $k$ 的连续段。目标是最大化选出的数的总和。其中，$1 \leq k \leq n \leq 10^5$。

题解

令 $f_i$ 表示考虑序列 $a[1 \dots i]$ 所能获得的最大和。为了计算 $f_i$，我们需要考虑 $a_i$ 是否被选中。如果 $a_i$ 被选中，那么它属于的最后一个连续段的起始位置 $j$ 必须满足 $j \geq i-k+1$。因此，转移方程可以写成：

$$ f_i = \max_{\substack{j=\min(i-k+1, 1) \\ \text{or } a_i \text{ not chosen }}}^{i+1} \{ \dots \} $$

如果我们假设 $a_i$ 总是被选中，那么我们需要找到一个前驱状态 $f_{j-1}$，其中 $j-1 < i-k+1$，使得 $f_i = f_{j-1} + \sum_{p=j}^i a_p$ 最大。令 $s$ 为前缀和，则 $\sum_{p=j}^i a_p = s_i - s_{j-1}$。因此：

$$ f_i = \max_{j-1 < i-k+1} \{ f_{j-1} - s_{j-1} \} + s_i $$

这形式上是一个单调队列优化的模板。对于每个 $i$，我们需要在之前的状态中找到 $\max \{f_{j-1} - s_{j-1}\}$。我们可以维护一个单调队列，存储形如 $(f_{idx} - s_{idx}, idx)$ 的对，并保证队列中 $f_{idx} - s_{idx}$ 的值单调递增。在计算 $f_i$ 时，移除队列中下标小于 $i-k$ 的元素，队头即为所需的最大值。

如果 $a_i$ 不被选中，则 $f_i = f_{i-1}$。因此，最终的 $f_i$ 需要取两种情况的最大值。

Luogu P1776 宝物筛选

题目描述

这是一个多重背包问题。有 $n$ 件物品，每件物品有价值 $v_i$，重量 $w_i$，数量 $m_i$。背包容量为 $W$。求在不超过背包容量的情况下，最大化总价值。其中，$1 \leq n \leq 100$，$\sum m_i \leq 10^5$，$0 \leq W \leq 4 \times 10^4$， $1 \leq n \leq 100$。

题解

二进制拆分可以将多重背包转化为 0/1 背包，时间复杂度为 $O(nW \log m)$。这里介绍 $O(nW)$ 的单调队列优化 DP 方法。

令 $f_{i, j}$ 表示考虑前 $i$ 件物品，总重量恰好为 $j$ 的最大价值。对于第 $i$ 件物品，我们可以选择 $k$ 件（$0 \leq k \leq m_i$）。转移方程为：

$$ f_{i, j} = \max_{0 \leq k \leq m_i, j - k w_i \geq 0} \{ f_{i-1, j - k w_i} + k v_i \} $$

这个转移方程看起来不太像单调队列优化的形式。我们注意到，对于相同的物品 $i$，不同重量 $j$ 的转移是相互关联的。如果我们将 $j$ 按照 $j \pmod{w_i}$ 分组，对于同一组内的 $j$，转移会变得规律。令 $j = q w_i + r$，其中 $0 \leq r < w_i$。此时，转移方程变为：

$$ f_{i, q w_i + r} = \max_{0 \leq k \leq m_i, q - k \geq 0} \{ f_{i-1, (q-k) w_i + r} + k v_i \} $$

令 $p = q - k$，则 $k = q - p$。方程变为：

$$ f_{i, q w_i + r} = \max_{0 \leq p \leq q} \{ f_{i-1, p w_i + r} + (q-p) v_i \} $$ $$ f_{i, q w_i + r} = \max_{0 \leq p \leq q} \{ f_{i-1, p w_i + r} - p v_i \} + q v_i $$

现在，对于固定的 $r$，当我们计算 $f_{i, q w_i + r}$ 时，需要查询 $f_{i-1, p w_i + r} - p v_i$ 在 $p$ 上的最大值。这正是单调队列优化的经典场景。我们对每个 $r$ 维护一个单调队列，队列中存储 $(f_{i-1, p w_i + r} - p v_i, p)$，并保证值单调递增。每次计算 $f_{i, q w_i + r}$ 时，移除队列中 $p > q$ 的元素，队头即为所需的最大值。整个 DP 的时间复杂度为 $O(nW)$。

Luogu P6563 \[SBCOI2020\] 一直在你身旁

题目描述

给定一个长度为 $n$ 的序列 $a$，其中 $a_1 \leq a_2 \leq \dots \leq a_n$。你需要猜测一个正整数 $x$ ($1 \leq x \leq n$)。你可以花费 $a_i$ 的价格来询问 $x$ 是否大于 $i$。求出至少需要花费多少钱才能保证猜中 $x$。多测，$\sum n \leq 7100$。

题解

令 $f_{i, j}$ 表示在确定 $i \leq x \leq j$ 的条件下，猜中 $x$ 所需的最小花费。这是一个区间 DP 问题。我们可以写出转移方程：

$$ f_{i, j} = \min_{k=i}^{j-1} \left\{ \max(f_{i, k}, f_{k+1, j}) + a_k \right\} $$

这个转移中的 $\max$ 运算使得直接优化困难。我们考虑固定 $i$，观察 $f_{i, j}$ 关于 $j$ 的性质。由于 $a_k$ 单调递增，且 $f_{i, j}$ 满足 $f_{i, j} \leq f_{i, j+1}$，我们可以通过二分或扫描找到一个分界点 $p$，使得 $i \leq k < p$ 时，决策主要由 $f_{k+1, j} + a_k$ 决定，而 $p \leq k \leq j$ 时，决策主要由 $f_{i, k} + a_k$ 决定。

更进一步，我们可以发现，当固定 $i$ 时，最优的询问点 $k$ 满足 $\max(f_{i, k}, f_{k+1, j}) + a_k$ 关于 $k$ 存在单调性。通过分析发现，对于固定的 $i$，最优的 $k$ 随着 $j$ 的增大而单调不减。这使得我们可以用扫描线或者分治的思想来优化。对于 $i$ 循环，维护一个单调队列来优化 $k+1$ 到 $j$ 的转移，以及另一个数据结构（可能也是单调队列或者简单扫描）来优化 $i$ 到 $k$ 的转移。最终时间复杂度可以优化到 $O(n^2)$。

Luogu P5665 \[CSP-S2019\] 划分

题目描述

给定一个长度为 $n$ 的序列 $a$。需要找到划分点 $1 \leq k_1 < k_2 < \dots < k_p < n$，使得划分出的各段和满足单调不减：$\sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \dots \leq \sum_{i=k_p+1}^{n} a_i$。在此基础上，最小化各段和的平方和：$(\sum_{i=1}^{k_1} a_i)^2 + (\sum_{i=k_1+1}^{k_2} a_i)^2 + \dots + (\sum_{i=k_p+1}^{n} a_i)^2$。其中，$2 \leq n \leq 4 \times 10^7$， $1 \leq a_i \leq 10^9$。

题解

设 $f_i$ 表示考虑序列 $a[1 \dots i]$，且最后一段的划分点是 $i$ 时（即最后一段为 $a[j+1 \dots i]$），满足条件的最小平方和。令 $s$ 为前缀和。那么最后一段的和为 $s_i - s_j$。我们需要在满足单调性的前提下，找到一个 $j$ 使得 $f_j + (s_i - s_j)^2$ 最小。这涉及到对 $j$ 的限制，使得 $s_i - s_j$ 单调递增。

一个关键性质是：在最优划分方案中，最后一段的和一定是所有合法划分方案中最小的。证明如下：设最优方案的最后一段和为 $S_{\text{last}}$。如果存在另一段 $S_k$ 使得 $S_k > S_{\text{last}}$，我们尝试调整：将 $S_{\text{last}}$ 增加 $\epsilon$，将 $S_k$ 减去 $\epsilon$（其中 $\epsilon > 0$ 且保证 $S_k - \epsilon \ge S_{\text{prev}}$， $S_{\text{last}} + \epsilon \le S_{\text{next}}$）。调整后的平方和为 $(S_k - \epsilon)^2 + (S_{\text{last}} + \epsilon)^2 = S_k^2 - 2\epsilon S_k + \epsilon^2 + S_{\text{last}}^2 + 2\epsilon S_{\text{last}} + \epsilon^2 = S_k^2 + S_{\text{last}}^2 + 2\epsilon(S_{\text{last}} - S_k) + 2\epsilon^2$。由于 $S_k > S_{\text{last}}$，所以 $S_{\text{last}} - S_k < 0$。当 $\epsilon$ 足够小时，$2\epsilon(S_{\text{last}} - S_k) + 2\epsilon^2 < 0$。因此调整后的平方和更小，这与最优性矛盾。所以最后一段和最小。

我们令 $f_i$ 表示考虑 $a[1 \dots i]$，最后一段为 $a[j+1 \dots i]$ 的最小平方和。令 $g_j = s_j - f_j$ （这个状态定义有点问题，应该另定义）。更准确的状态是，设 $f_i$ 为考虑 $a[1 \dots i]$ 的最小平方和，且最后一段的最后一个元素是 $a_i$。转移方程为：

$$ f_i = \min_{0 \leq j < i} \{ f_j + (s_i - s_j)^2 \} $$

同时需要满足 $s_i - s_j \geq s_j - s_k$ （如果 $j$ 的前一段是 $k$）。

一个更有效的 $O(n)$ DP 状态定义：令 $f_i$ 表示考虑 $a[1 \dots i]$ 的最小平方和。设 $last\_sum_i$ 为最优划分方案中，最后一段的和。那么 $f_i = f_{j} + (s_i - s_j)^2$，其中 $j$ 是最后一个分段点，且 $s_i - s_j \geq last\_sum_j$。

考虑用单调队列优化。我们需要维护一个关于 $j$ 的单调队列，使得 $s_i - s_j$ 能够满足单调性。令 $val_j = s_j - last\_sum_j$。那么我们要求 $s_i \geq val_j$。维护一个单调队列，其中存储的 $j$ 对应的 $val_j$ 是单调递增的。每次计算 $f_i$，从队头弹出不满足 $s_i \geq val_j$ 的 $j$。队头元素即为最优的 $j$。然后，将新的决策点 $(i, s_i - f_i)$ 加入队列，并维护队列的单调性。

具体实现时，注意压位高精和空间优化。