双端栈、双端队列 与 单调队列

const int N = 100005;
int s[N], top1 = 0, top2 = N - 1;   // 数组下标 1..N-1 都可用

bool full() { return top1 + 1 == top2; }   // 两指针相邻 = 满

bool pushL(int x) {                    // 左栈：向右生长
    if (full()) return false;
    s[++top1] = x;
    return true;
}
bool pushR(int x) {                    // 右栈：向左生长
    if (full()) return false;
    s[--top2] = x;
    return true;
}
int popL() { return top1 == 0    ? -1 : s[top1--]; }
int popR() { return top2 == N - 1 ? -1 : s[top2++]; }
int topL() { return top1 == 0    ? -1 : s[top1]; }
int topR() { return top2 == N - 1 ? -1 : s[top2]; }

const int MAXN = 2000005;
int q[MAXN];
int h = MAXN / 2, t = MAXN / 2 - 1;   // h = 队头下标, t = 队尾下标
// 约定：h > t 表示队空；元素存放在 q[h .. t] 这段连续区间内

// ---------- 队尾操作 ----------
void push_back(int x) { q[++t] = x; }
void pop_back()       { t--; }
int  back()           { return q[t]; }

// ---------- 队头操作 ----------
void push_front(int x) { q[--h] = x; }
void pop_front()       { h++; }
int  front()           { return q[h]; }

// ---------- 通用 ----------
bool empty() { return h > t; }
int  size()  { return t - h + 1; }

const int N = 1000005;
int n, k, a[N];
int q[N], h = 1, t = 0;      // q 存下标；h > t 表示队空

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++) {
        // ① 过期弹出：队首下标已经滑出窗口左边界 i-k+1
        while (h <= t && q[h] < i - k + 1) h++;

        // ② 队尾淘汰：新元素更小（或相等），队尾永远没机会
        while (h <= t && a[q[t]] >= a[i]) t--;

        // ③ 入队 + 取值
        q[++t] = i;
        if (i >= k) printf("%d ", a[q[h]]);
    }
}

#include <bits/stdc++.h>
using namespace std;
int n, k, a[1000005];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    deque<int> q;                    // 存下标
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() < i - k + 1) q.pop_front();  // ①
        while (!q.empty() && a[q.back()] >= a[i])      q.pop_back();   // ②
        q.push_back(i);                                                 // ③
        if (i >= k) printf("%d ", a[q.front()]);
    }
}

const int N = 3000005;
int n, a[N], ans[N], st[N], top = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++) {
        // 栈顶元素比 a[i] 小 → a[i] 就是它的「下一个更大」
        while (top && a[st[top]] < a[i]) {
            ans[st[top]] = i;      // 记录是「第几个位置」，也可以记 a[i]
            top--;
        }
        st[++top] = i;             // 自己入栈，等后面的元素来找
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i] ? a[ans[i]] : -1);   // ans 存的是下标，输出值要再取一次 a
    return 0;
}

dp[i] = max / min { dp[j] + w(i) }    其中 j 属于区间 [L(i), R(i)]

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, m, q[N], h = 1, t = 0;
long long S[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        S[i] = S[i - 1] + x;              // 前缀和
    }

    long long ans = LLONG_MIN;
    q[++t] = 0;                            // 关键：把 S[0] 先放进去，代表「从头开始取」
    for (int i = 1; i <= n; i++) {
        // ① 过期：k 必须不小于 i-m
        while (h <= t && q[h] < i - m) h++;
        ans = max(ans, S[i] - S[q[h]]);       // ② 用队首（区间内 S 最小）转移
        // ③ 把 S[i] 入队，保持 S 值递增（求最小）
        while (h <= t && S[q[t]] >= S[i]) t--;
        q[++t] = i;
    }
    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, k, a[N];
int q[N], h, t;                        // 单调队列（存下标）

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // ---------- 第一遍：求每个窗口的最小值 ----------
    h = 1, t = 0;
    for (int i = 1; i <= n; i++) {
        while (h <= t && q[h] < i - k + 1) h++;      // 过期
        while (h <= t && a[q[t]] >= a[i]) t--;            // 队内递增
        q[++t] = i;
        if (i >= k) printf("%d ", a[q[h]]);
    }
    puts("");

    // ---------- 第二遍：求每个窗口的最大值（不等号反向） ----------
    h = 1, t = 0;
    for (int i = 1; i <= n; i++) {
        while (h <= t && q[h] < i - k + 1) h++;
        while (h <= t && a[q[t]] <= a[i]) t--;            // 队内递减
        q[++t] = i;
        if (i >= k) printf("%d ", a[q[h]]);
    }
    puts("");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int n, m, a[N], q[N], h = 1, t = 0;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++) {
        while (h <= t && q[h] < i - m) h++;          // ① 过期：下标 < i-m

        if (i == 1) printf("0\n");                 // ② 取答案（此时队列里是 [i-m, i-1] 的候选）
        else       printf("%d\n", a[q[h]]);

        while (h <= t && a[q[t]] >= a[i]) t--;         // ③ 入队前先淘汰队尾
        q[++t] = i;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
long long S[N];

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        S[i] = S[i - 1] + x;
    }

    deque<int> q;                       // 存前缀和的下标 k，S[q] 递增
    q.push_back(0);                        // 陷阱1：S[0] 必须先入队
    long long ans = LLONG_MIN;

    for (int i = 1; i <= n; i++) {
        // 陷阱2：k 的取值范围是 [i-m, i-1]（不含 i）
        while (!q.empty() && q.front() < i - m) q.pop_front();

        ans = max(ans, S[i] - S[q.front()]);       // 用队首（最小前缀和）转移

        while (!q.empty() && S[q.back()] >= S[i]) q.pop_back();  // 陷阱3：维护 S 递增
        q.push_back(i);
    }
    printf("%lld\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a, b, n;
int g[N][N], rm[N][N], rn[N][N], cm[N][N], cn[N][N];
int q[N], h, t;

// 对长度为 len 的一维数组 v 做窗口大小 n 的最值，结果写入 out（mx=1 求最大）
void slide(int* v, int len, int* out, int mx) {
    h = 1, t = 0;
    for (int i = 1; i <= len; i++) {
        while (h <= t && q[h] < i - n + 1) h++;
        while (h <= t && (mx ? v[q[t]] <= v[i] : v[q[t]] >= v[i])) t--;
        q[++t] = i;
        if (i >= n) out[i - n + 1] = v[q[h]];
    }
}

int main() {
    scanf("%d%d%d", &a, &b, &n);
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++) scanf("%d", &g[i][j]);

    // 第 1、2 步：逐行做窗口最值（行方向）
    for (int i = 1; i <= a; i++) {
        slide(g[i], b, rm[i], 1);   // 行最大值
        slide(g[i], b, rn[i], 0);   // 行最小值
    }

    // 第 3、4 步：逐列做窗口最值（列方向），先取列数组再调用 slide
    int col[N], out[N], cols = b - n + 1;
    for (int j = 1; j <= cols; j++) {
        for (int i = 1; i <= a; i++) col[i] = rm[i][j];
        slide(col, a, out, 1);
        for (int i = 1; i <= a - n + 1; i++) cm[i][j] = out[i];

        for (int i = 1; i <= a; i++) col[i] = rn[i][j];
        slide(col, a, out, 0);
        for (int i = 1; i <= a - n + 1; i++) cn[i][j] = out[i];
    }

    // 第 5 步：逐格相减取最小
    int ans = INT_MAX;
    for (int i = 1; i <= a - n + 1; i++)
        for (int j = 1; j <= cols; j++)
            ans = min(ans, cm[i][j] - cn[i][j]);

    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, h[N], L[N], R[N], st[N];

int main() {
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= n; i++) scanf("%d", &h[i]);

        // 左边界：左边第一个严格矮于 h[i] 的下标
        int top = 0;
        for (int i = 1; i <= n; i++) {
            while (top && h[st[top]] >= h[i]) top--;
            L[i] = top ? st[top] : 0;      // 0 表示左边没有更矮的
            st[++top] = i;
        }
        // 右边界：右边第一个严格矮于 h[i] 的下标
        top = 0;
        for (int i = n; i >= 1; i--) {
            while (top && h[st[top]] >= h[i]) top--;
            R[i] = top ? st[top] : n + 1;    // n+1 表示右边没有更矮的
            st[++top] = i;
        }
        long long ans = 0;
        for (int i = 1; i <= n; i++)
            ans = max(ans, (long long)h[i] * (R[i] - L[i] - 1));
        printf("%lld\n", ans);
    }
    return 0;
}

dp[i] = a[i] + max{ dp[j] }   其中 j < i、可跳到、且 d-g ≤ i-j ≤ d+g（或 i < d-g 时起点直接可达）

dp[r + k·w] = max over j ∈ [max(0, k-c), k-1] { dp[r + j·w] + (k - j)·v }
            = k·v + max over j ∈ [max(0, k-c), k-1] { dp[r + j·w] - j·v }

// q 存下标，h/t 为队头/队尾指针，初值 h = 1, t = 0（队空）
for (int i = 1; i <= n; i++) {
    while (h <= t && q[h] < i - k + 1) h++;      // ① 过期弹出
    while (h <= t && a[q[t]] >= a[i]) t--;            // ② 队尾淘汰（求最大改 <=）
    q[++t] = i;                                        // ③ 入队
    if (i >= k) printf("%d ", a[q[h]]);            // ④ 取答案（窗口满才输出）
}

// st 存下标，top 为栈顶指针，初值 top = 0（栈空）
for (int i = 1; i <= n; i++) {
    while (top && a[st[top]] < a[i]) {                 // 栈顶找到了「下一个更大」
        ans[st[top]] = i;      // 或 a[i]；求严格更大用 <，非严格用 <=
        top--;
    }
    st[++top] = i;
}
// 循环结束后仍在栈里的下标 → 答案为 -1 / 0