https://chicago01.top

单调队列

需要满足两个性质：

1. 队列内具有一定的单调性（优先队列）。
2. 满足普通队列性质，一端进，另一端出，不可以中间插队。

但是这样就会现矛盾了，例如一个单调增的队列：1,5,8,9，我们要插入4，这时如果只能从尾端进去的话就打破了其单调性，呢么这时的做法就是从队尾到队头，把大于4的全部T了，然后插入后的队列就变成了1,4。

应用

常用于优化动态规划（DP）问题。

例 最大子序和

输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。

输入格式

第一行输入两个整数n,m。

第二行输入n个数，代表长度为n的整数序列。

同一行数之间用空格隔开。

输出格式

输出一个整数，代表该序列的最大子序和。

数据范围

$1≤n,m≤300000$

输入样例：

6 4
1 -3 5 1 -2 3

输出样例：

7

题解

先占个坑。

代码

//官方代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 300006, INF = 0x3f3f3f3f;
int n, m, s[N], q[N];

int main() {
    cin >> n >> m;
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] += s[i-1];
    }
    int l = 1, r = 1, ans = -INF;
    q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while (l <= r && q[l] < i - m) l++;
        ans = max(ans, s[i] - s[q[l]]);
        while (l <= r && s[q[r]] >= s[i]) r--;
        q[++r] = i;
    }
    cout << ans << endl;
    return 0;
}