单调队列

顾名思义

单调队列这个名字就指明了它的性质——单调性

说单调队列，那我们就先说说这个单调队列是个什么物种。单调队列从字面上看，无非就是有某种单调性的队列，没错，这就是所谓的单调队列。 单调队列它分两种，一种是单调递增的，另外一种是单调递减的。

在这搬出百度百科的解释：不断地向缓存数组里读入元素，也不时地去掉最老的元素，不定期的询问当前缓存数组里的最小的元素。

用单调队列来解决问题，一般都是需要得到当前的某个范围内的最小值或最大值。

先摆出一个滑动窗口的模板供大家学习与参考，如有错误，望读者批评指正

typedef long long ll;
const int maxn=;
int a[maxn],qmax[maxn],qmin[maxn],savemax[maxn],savemin[maxn];
int main(){
   int n,k,cnt=1;
   scanf("%d%d",&n,&k);
   for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
   int beg=1,top=0;//beg为qmax的队列的头（**记住队列存的是数组下标**），top为qmax的尾（不包括头）
   int st=1,ed=0;//beg为qmin的队列的头（**记住队列存的是数组下标**），top为qmin的尾（不包括头）
   for(int i=1;i<=n;i++){
	while(beg<=top&&a[i]>=a[qmax[top]]) top--;//保证队列中从头到尾的所映射的a[]是呈现递减形式（也就是说qmax存的是a[]下标）
	qmax[++top]=i;
	while(st<=ed&&a[i]<=a[qmin[ed]]) ed--;//保证队列中从头到尾的所映射的a[]是呈现递增形式（也就是说qmin存的是a[]下标）
	qmin[++ed]=i;
	if(i>=k){//i含义是窗口的最右端下标，所以当i>=k的时候，窗口已经形成。因此，可以选择最大值和最小值。
		while(qmax[beg]<=i-k) beg++;//每个窗口的最左端都是一个确定值，所以要移动队列的头使得它的映射值（原数组下标）在窗口里面
		while(qmin[st]<=i-k) st++;
		savemax[cnt]=a[qmax[beg]];//save就是保存值
		savemin[cnt]=a[qmin[st]];
		cnt++;
	}
   }
   return 0;
}

这道滑动窗口的题目告诉我们，对于这种求窗口（移动区间且区间长度是固定值的）最大值与最小值的方法可以用单调队列
复杂度估计是o(n),如有错误，望读者批评指正

当你理解上面的窗口问题，发现下面这道题的时候就感觉太简单了。

附上AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
int a[maxn],q[maxn];
int main(){
   int n,k;
   scanf("%d%d",&n,&k);
   for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
   int beg=1,top=0;
   for(int i=1;i<=n;i++){
	while(beg<=top&&a[i]>=a[q[top]]) top--;
	q[++top]=i;
	if(i>=k){
		while(q[beg]<=i-k) beg++;
		printf("%d\n",a[q[beg]]);
	}
   }
   return 0;
}

逛画展，hc大佬说这题可以用单调队列写，但是我owo不会，我只会用尺取法模拟，如果想知道尺取法怎么写的话，可以参考下面的AC代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define pa pair<int, int>
typedef long long ll;
const int maxn=1e6+5;
int vis[2005],a[maxn];
int main(){
    int n,m,cnt=0;
    pa ans;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int beg=1,top=2;
    vis[a[1]]++;
    cnt++;
    ans.first=1;ans.second=n;
    while(top<=n){
        if(!vis[a[top]])
            cnt++;
        vis[a[top]]++;
        if(cnt==m){
            while(vis[a[beg]]>=2){
                vis[a[beg]]--;
                beg++;
            }
            if(top-beg<ans.second-ans.first)
                ans.first=beg,ans.second=top;
            vis[a[beg]]--;
            beg++;
            cnt--;
        }
        top++;
    }
    if(m==1)
        printf("1 1\n");
    else
        printf("%d %d\n",ans.first,ans.second);
   return 0;
}

琪露诺
这道题我要好好写一下题解，毕竟花了2天才真正理解的。网上有很多代码是错误的，所以大家要好好理解。Hack数据
5 3 4
0 1 2 3 4 5
正确答案是4，而很多代码答案是5。

思路分析
我们先设dp[i]表示在位置编号为i时的最大冰冻指数值。很容易发现在位置编号为[n+1-r,n]区间的任意一个值都可以通过走l~r步到达对岸，所以我们就把问题转化为到求max(dp[i]) (i属于[n+1-r,n])。
那我们怎样求解dp[i]呢？
不难发现一个简单的递推式 $dp\left[i\right]=max\left(dp\right[j\left]\right)+a\left[i\right],j属于[i-r,i-l]$dp[i]=max(dp[j])+a[i],j属于[i−r,i−l]
这样写出的代码如下

for(i属于l~r){
	for(j属于max(i-r,0)~i-l)
		dp[i]=max(dp[i],dp[j]+a[i])
}

很明显，如果l-r的长度取为n，那么复杂度就是o(n^2),而且n=1e5,所以对于1s的时间是远远不够的。
那我们怎样用更快速的方法求dp[i]呢？
我们看看上面的代码，发现i每增加一，j的左右区间加一，也就相当于区间移动（其实开头那部分区间是边移动边拓宽的，这个不理解没关系，继续往下看）。这不就是窗口滑动问题吗？可以采用优先队列解决该问题。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
ll mypow(ll a,ll n){
    ll num=a,sum=1;
    while(n){
        sum*=num;
        n--;
    }
    return sum;
}//我一般不用cmath的pow函数，那个返回值是double,容易出现精度损失。所以我建议大家自己写mypow函数
const ll inf=-mypow(2,31);
ll a[maxn],q[maxn],dp[maxn];//a[]储存数据 q[]模拟优先队列 dp[]记录答案
int main(){
    ll ans=inf;
    int n,l,r;
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++)
        scanf("%lld",&a[i]);
    dp[0]=a[0];
    for(int i=1;i<=n;i++)
        dp[i]=inf;
    int beg=1,top=0,cnt=0;//cnt表示的是dp[]取值的下标
    for(int i=l;i<=n;i++){
        while(beg<=top&&dp[q[top]]<=dp[cnt]) top--;
        q[++top]=cnt;
        while(q[beg]+r<i) beg++;
        dp[i]=dp[q[beg]]+a[i];
        cnt++;
        if(i>=n+1-r)//答案更新
            ans=max(ans,dp[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

切蛋糕
这一题我一定要好好写个题解。有两个原因，一个是我终于自己独立写出一道不是那么水的优先队列题目，另一个是网上AC代码有hack数据，但是那些数据hack不了我的代码。
Hack数据

1 1
5
答案是5
5 2
1 -10 -10 -10 -10
答案是1
4 3
1 2 4 -6
答案是7
5 2
5 -5 1 -2 -1
答案是5 

思路分析
连续k块蛋糕幸运值之和------->与区间和有关（前缀和）
设prefix[i]为前i项的幸运值总和
补充说明：
prefix[i]-prefix[j] (i>=j)
表示的是a(j~i]的总和（不包括a[j]）
prefix[i]-prefix[j]+a[j] (i>=j)
表示的是a[j~i]的总和（包括a[j]）

1.当我们把前缀和预处理之后，我们发现只要在[i,min(i+m-1)]（i属于【1，n】）找到区间的最小值和最大值然后保证最大值的下标大于等于最小值下标就可以用最大值-最小值的值赋给ans,然后max(ans,ans+a[st]);(如果不能理解，看上面补充说明)

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
typedef long long ll;
ll a[maxn],prefix[maxn],qx[maxn],qd[maxn];
ll mypow(ll a,ll n){
    ll num=a,sum=1;
    while(n){
        sum*=num;
        n--;
    }
    return sum;
}
int main(){
    int n,m;
    ll ans=-mypow(2,31);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    scanf("%lld",&a[i]);
    prefix[i]=prefix[i-1]+a[i];
    }
    int beg=1,top=0,st=1,ed=0;
    for(int i=1;i<=n;i++){
    while(beg<=top&&prefix[qd[top]]<=prefix[i]) top--;
    while(st<=ed&&prefix[qx[ed]]>=prefix[i]) ed--;
    qd[++top]=i;qx[++ed]=i;
    while(qd[beg]+m-1<i) beg++;
    while(qx[st]+m-1<i) st++;
    if(qd[beg]>=qx[st]){
        ll tmp=max(prefix[qd[beg]]-prefix[qx[st]],prefix[qd[beg]]-prefix[qx[st]]+a[qx[st]]);
        ans=max(ans,tmp);
    }
    }
    printf("%lld\n",ans);
    return 0;
}

希望这篇文章可以帮助大家更好地理解单调队列，如果大家有好的单调队列题目望大家分享一下题号。