单调队列

单调队列常用于解决定长区间最值问题（滑动窗口），一般使用一个 deque 来实现。

与单调栈类似，每次向队尾 push 新元素时，新元素显然“离得近”，如果新元素不仅“离得近”，优先级还比当前队尾元素更高（更大/小），那么在以后当前队尾元素必然不可能成为答案，可以将其 pop_back 弹出。由于求解的是区间最值，因此单调队列的队首即为答案，注意每次取出答案前要先检查队首元素是否“过期”，即在当前区间内。

P2032

裸的板子题。

#include <bits/stdc++.h>
using namespace std;
int n, k, a[maxN];
void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    deque<int> q;
    for (int i = 0; i < n; i++) {
        while (!q.empty() && a[q.back()] < a[i]) {
            q.pop_back();
        }
        while (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }
        q.push_back(i);
        if (i >= k - 1) {
            cout << a[q.front()] << endl;
        }
    }
}
int main() {
    solve();
    return 0;
}

P2216

实际上是一个二维的滑动窗口问题。先对每行求一个区间最值，再对列求一个“行区间最值的最值”，就可以求出一个二维区域的最值。两步操作都可以用一个单调队列来实现。

#include <bits/stdc++.h>
using namespace std;
#define mi(x, y) ((x) < (y) ? x : y)
const int inf = 0x7fffffff, maxN = 2e5 + 5;
int a, b, n, m[1005][1005], maxx[1005][1005], minn[1005][1005], res = inf; // 表示第i行第j列往左n个数的最大最小值
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> a >> b >> n;
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            cin >> m[i][j];
        }
    }
    for (int i = 1; i <= a; i++) {
        deque<int> qmax, qmin;
        for (int j = 1; j <= b; j++) {
            while (!qmax.empty() && m[i][j] >= m[i][qmax.back()]) {
                qmax.pop_back();
            }
            while (!qmax.empty() && qmax.front() <= j - n) {
                qmax.pop_front();
            }
            qmax.push_back(j);
            maxx[i][j] = m[i][qmax.front()];
            while (!qmin.empty() && m[i][j] <= m[i][qmin.back()]) {
                qmin.pop_back();
            }
            while (!qmin.empty() && qmin.front() <= j - n) {
                qmin.pop_front();
            }
            qmin.push_back(j);
            minn[i][j] = m[i][qmin.front()];
        }
    }
    for (int j = n; j <= b; j++) {
        deque<int> qmax, qmin;
        for (int i = 1; i <= a; i++) {
            while (!qmax.empty() && maxx[i][j] >= maxx[qmax.back()][j]) {
                qmax.pop_back();
            }
            while (!qmax.empty() && qmax.front() <= i - n) {
                qmax.pop_front();
            }
            qmax.push_back(i);
            while (!qmin.empty() && minn[i][j] <= minn[qmin.back()][j]) {
                qmin.pop_back();
            }
            while (!qmin.empty() && qmin.front() <= i - n) {
                qmin.pop_front();
            }
            qmin.push_back(i);
            if (i >= n)
                res = mi(res, maxx[qmax.front()][j] - minn[qmin.front()][j]);
        }
    }
    cout << res;
    return 0;
}

CF1918D

二分答案，check 函数内进行单调队列优化 dp。

dp[i] 表示阻塞 a[i]，阻塞元素总和的最小值。每次转移，找前面所有满足“到 i 的这一段元素总和不超过 x”的位置里，dp 值最小的那一个进行转移。

//O2优化
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define mi(x, y) ((x) < (y) ? (x) : (y))
#define ma(x, y) ((x) > (y) ? (x) : (y))    
const int maxN = 2e5 + 5;
const long long inf = 1e18;
int n, a[maxN];
long long dp[maxN], sum[maxN];
bool check(long long x) {
    deque<int> q;
    q.push_back(0);
    for (int i = 1; i <= n + 1; i++) {
        dp[i] = dp[q.front()] + a[i];
        while (!q.empty() && dp[q.back()] >= dp[i]) {
            q.pop_back();
        }
        while (!q.empty() && sum[i] - sum[q.front()] > x) {
            q.pop_front();
        }
        q.push_back(i);
    }
    return dp[n + 1] <= x;
}
void solve() {
    long long l = -1, r = 0, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        l = ma(l, a[i]), r += a[i];
    }
    a[n + 1] = 0;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        if (check(mid)) {
            res = mid, r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << res << '\n';
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}