单调队列（小）总结
最近，看到了自己洛谷任务计划队列中越堆越多，为了防止咕咕咕，我就来写一写单调队列，清一清计划。
首先，我们先来看一道题： P1886 滑动窗口。
题目描述
现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3。
输入格式
输入一共有两行，第一行为n,k。
第二行为n个数(x<INT_MAX)
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值。
输入输出样例
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7
数据范围
50%的数据，(n<=10^5)
100%的数据，(n<=10^6)
这道题其实是属于单调队列的基础题，通过这道题就可以了解到单调队列。
法1：暴力法
我们可以考虑每一次滑动之后，我们枚举长度为k的序列，最后求出最大最小值。
当然，这样的时间复杂度((n*k))是无法过掉这道题的。
法2：单调队列
我们可以来简单分析一下这个样例，这样更有助于我们理解单调队列。
{1,3,-1,-3,5,3,6,7}
首先，我们来看一下当k=3的时候的最小值。
[1,3,-1] 此时，最小值为-1。
[3,-1,-3] 此时，最小值为-3。
[-1,-3,5] 此时，最小值为-3。
我们可以发现，当加入比当前最小值大的数时，这个数是不对答案做出贡献的。
所以，我们可以这样思考，
对于一个空的队列来说，我们首先会先把(1)加入进来，
然后再来看下一个数，我们发现3是有可能当做最优值的（就是当1不合法的时候），所以，我们就可以将3也加入到队列中。
然后，下一个数(-1)，我们发现-1<3,只要有-1存在时，3永远不可能作为最优解，所以我们就可以把3丢掉，（丢掉，全部丢掉），然后，看一下1，也是这个道理，所以我们就把1丢掉，然后再把-1加入队列中。
对于每一次，我们都要去判断一下队头是否是符合条件的，如果不符合条件，那么就直接将其踢出。 （这里非常感谢zzh同学指明我上一次讲解的思路不足）
所以，我们就可以将单调队列的基本规律写一下。
加入操作时，我们需要将要加入的元素和队尾的元素进行比较，那个更优，如果当前的元素更优，那么就将队尾的元素踢出，一直踢到不能为止。
我们再判断一下队首的元素满不满足条件，如果不满足的话就将队首的元素踢出。这样队列中就保持了 $$ 单调性 $$这一性质，我们就可以得到题目中的所要求的最值。
下面，我们讲了这么多就可以直接上代码了（大家一定都会了）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int head,tail,p[maxn],q[maxn],i,n,a[maxn],k;
void _min(){
head=1;
tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&p[tail]>=a[i]) tail--;//进行踢出处理
p[++tail]=a[i];//将这个点加入队尾
q[tail]=i;//标记这个点的位置
if(q[head]<=i-k) ++head;
if(i>=k) printf("%d ",p[head]);
}
}
void _max(){
head=1;
tail=0;
for(int i=1;i<=n;i++){
while(head<=tail&&p[tail]<=a[i]) tail--;
p[++tail]=a[i];
q[tail]=i;
if(q[head]<=i-k) ++head;
if(i>=k) printf("%d ",p[head]);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
_min();
printf("
");
_max();
return 0;
}
这道题算是属于单调队列的入门题目，也可以帮助大家理解单调队列的原理。
下面我们来看下一道例题，是一道使用单调队列优化dp
P2569 [SCOI2010]股票交易
我们来总结一下这道题的题意(算是一句话题意吧)：
我们现在知道了这一段时间(T)内的股票的买入((AP_i))卖出((BP_i))价和最多买入((AS_i))卖出((BS_i))的数量限制，以及我们最多可以有(MAXP)支股票和交易之间需要间隔的时间(W)。
首先
我们可以很简单的看出来这是一道dp题，而且动态规划方程也不是很难想,状态的话我们可以这样考虑，因为数据范围中是(leq 2000),所以，我们完全可以开出一个2000*2000的数组。所以，我们第一维就很理所当然的表示出时间。第二维的话我们就可以将拿的股票数作为状态。这样我们就可以将状态列了出来(f[i][j])表示在前(i)天有(j)支股票时的最大收益。
现在我们来考虑一下如何将状态进行转移
Case 1：
在什么都没有的情况下直接进行购买（又称，裸买）其余的状态赋为(-inf)
Case 2:
不买也不卖的情况下，我们可以直接进行转移。
Case 3:
这里是最麻烦的一部分了，（菜鸡请自行离开，对，就是我），我们这里就是在我们买过的基础上再去买票。
首先，我们要去考虑一下题目上最前面的那个(W)天，我们知道每两次交易的时间要间隔(W)天，所以我们在更新的时候上一次交易的时间间隔就是在(i-w-1)的时候。有的人可能会问了，为什么不会是(i-2-w)
而偏偏是(i-1-w)呢 （因为你傻） 这是因为如果是(i-2-w)的话我们会在前面的时候进行更新，所以我们就不会有这个问题。
我们就可以设(i-1-w)天时有k支股票，因为有限制最多(as[i])的限制，所以我们就可以把这个转移方程列了出来
Case 4:
解决完在原有情况下的买入，我们就可以类比一下很快解决出卖出的状态转移方程。
这样我们就把最基础的状态转移方程推了出来
这时，我们发现整个转移下来所需要的时间复杂度是三次方的，这明显是过不了的，我们就可以考虑使用单调队列来进行优化。
我们可以来看一下这个最初的状态转移方程，
我们来拆分一下
因为我们要转移(f[i][j]) 所以，我们可以将(j)提出来，这样我们的方程就可以转化为
这个时候，我们就可以发现我们找到了在转移的时候我们要取到最大值，所以，这个时候我们就可以使用单调队列来进行优化。
同理，我们对于情况4也一样适用的，我们可以将转移方程转化一下，
所以，我们就可以使用单调队列来进行转移了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
template<typename type>
void scan(type &x){
type f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
#define itn int
const int N=2007;
int n,maxp,w,as,ap,bs,bp,f[N][N],qu[N];
int l,r,ans=0;
int main(){
scan(n);scan(maxp);scan(w);
memset(f,128,sizeof(f));//当赋值为127时，此时赋值的是最大值，当为128时，此时赋值时最小值
for(int i=1;i<=n;i++){
scan(ap);scan(bp);scan(as);scan(bs);
for(int j=0;j<=as;j++){
f[i][j]=-1*j*ap;//情况1
}
for(int j=0;j<=maxp;j++){
f[i][j]=max(f[i][j],f[i-1][j]);//情况2
}
if(i<=w)continue;
l=1;r=0;
for(int j=0;j<=maxp;j++){
while(l<=r&&qu[l]<j-as)l++;//踢出不合法的选项
while(l<=r&&f[i-w-1][qu[r]]+qu[r]*ap<=f[i-w-1][j]+j*ap)r--;
qu[++r]=j;
if(l<=r)
f[i][j]=max(f[i][j],f[i-1-w][qu[l]]+qu[l]*ap-j*ap);//如果队列中有符合条件的数值，我们就可以将方程进行转移
}
l=1,r=0;
for(int j=maxp;j>=0;j--){
while(l<=r&&qu[l]>j+bs)l++;
while(l<=r&&f[i-w-1][qu[r]]+qu[r]*bp<=f[i-w-1][j]+j*bp)r--;
qu[++r]=j;//同理
if(l<=r){
f[i][j]=max(f[i][j],f[i-w-1][qu[l]]+qu[l]*bp-j*bp);
}
}
}
for(int i=0;i<=maxp;i++){
ans=max(ans,f[n][i]);
}
printf("%d
",ans);
return 0;
}
这道题我们就可以是使用单调队列成功的优化一下dp从而切掉。_
下面，我们来看一道省选题（二维单调队列）
P2216 [HAOI2007]理想的正方形
一句话题意：有一个(a*b)的整数组成的矩阵，现请你从中找出一个(n*n)的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
题目分析：
我们不难发现，这个时候，我们不仅要维护一个最大的信息，我们还要维护一个最小的信息。所以我们就要进行两次的单调队列的转移，这样我们就可以
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template <typename type>
void scan(type &x){
type f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
const int N=1e3+8;
#define itn int
int n,m,k,ans=1e9;
int a[N][N],p[N],q[N];
int x[N][N],y[N][N];
int xx[N][N],yy[N][N];
void init(){
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
}
void work1(itn id){//处理列
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l<=r&&p[r]<=a[id][i])//取最大值
r--;
p[++r]=a[id][i];
q[r]=i;
while(q[l]<=i-k)l++;//不满足选的条件的话，将左边舍去
if(i>=k)x[id][i-k+1]=p[l];//在行确定的时候，在满足题目条件的情况下，统计每一列的答案
}
init();//清空
l=1;r=0;
for(int i=1;i<=m;i++){
while(l<=r&&p[r]>=a[id][i])
r--;
p[++r]=a[id][i];
q[r]=i;
while(q[l]<=i-k)l++;
if(i>=k)xx[id][i-k+1]=p[l];
}
}
void work2(itn id){
int l=1,r=0;
for(int i=1;i<=n;i++){
while(l<=r&&p[r]<=x[i][id])r--;
p[++r]=x[i][id];
q[r]=i;
while(q[l]<=i-k)l++;
if(i>=k)y[i-k+1][id]=p[l];
}
init();
l=1,r=0;
for(itn i=1;i<=n;i++){
while(l<=r&&p[r]>=xx[i][id])r--;
p[++r]=xx[i][id];
q[r]=i;
while(q[l]<=i-k)l++;
if(i>=k)yy[i-k+1][id]=p[l];
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scan(n);scan(m);scan(k);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scan(a[i][j]);
}
}
for(int i=1;i<=n;i++)work1(i);
for(int j=1;j<=m;j++)work2(j);
for(int i=1;i<=n-k+1;i++){
for(int j=1;j<=m-k+1;j++){
// printf("%d %d
",y[i][j],yy[i][j]);
ans=min(ans,y[i][j]-yy[i][j]);
}
}
printf("%d
",ans);
return 0;
}
下一道题:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template <typename type>
void scan(type &x){
type f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
#define itn int
const int N=2007;
int m,n,a,b,c,d,ans=0;
int gra[N][N],x[N][N],y[N][N],flo[N][N];
int s[N][N],q[N],p[N];
void init(){
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
}
void work1(int id){
init();
int l=1,r=0,len=b-d-1;
for(int i=1;i<=m;i++){
while(l<=r&&p[r]>=flo[id][i])r--;
p[++r]=flo[id][i];
q[r]=i;
while(q[l]<=i-len)l++;
if(i>=len)x[id][i-len+1]=p[l];
}
}
void work2(int id){
init();
int l=1,r=0,len=a-c-1;
for(int i=1;i<=n;i++){
while(l<=r&&p[r]>=x[i][id])r--;
p[++r]=x[i][id];
q[r]=i;
while(q[l]<=i-len)l++;
if(i>=len)y[i-len][id-1]=p[l];
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scan(n);scan(m);scan(a);scan(b);scan(c);scan(d);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scan(s[i][j]);
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for(int i=1;i<=n-a+1;i++){
for(itn j=1;j<=m-b+1;j++){
gra[i][j]=s[i+a-1][j+b-1]-s[i+a-1][j-1]-s[i-1][j+b-1]+s[i-1][j-1];
}
}
for(int i=1;i<=n-c+1;i++){
for(itn j=1;j<=m-d+1;j++){
flo[i][j]=s[i+c-1][j+d-1]-s[i+c-1][j-1]-s[i-1][j+d-1]+s[i-1][j-1];
}
}
for(int i=1;i<=n;i++)work1(i);
for(itn i=1;i<=m;i++)work2(i);
for(itn i=1;i<=n-a+1;i++){
for(int j=1;j<=m-b+1;j++){
ans=max(ans,gra[i][j]-y[i][j]);
}
}
printf("%d
",ans);
return 0;
}
是我太懒了，所以后半部分就先咕到这里吧。