【5】单调队列学习笔记

前言

鸽了很久，$2023/1/5$ 开始，$2023/1/21$ 才完工。

中途去集训了，没时间来补漏洞。

单调队列

单调队列是一种非常实用的数据结构，可以用于查询一个定长区间在以一定速度向后滑动，并查询区间内最值的问题（具体见例题 $1$ ）。时间复杂度非常低，总体是 $O(n)$ ，均摊到每个元素是 $O(1)$ ，所以常用来优化其他算法。

单调队列需要保证队列元素的单调性，也就是说，要保证队头就是最值，这样就可以做到 $O(1)$ 查询最值。

单调队列的维护：

$1$ ：向后滑动的过程中，会有新的元素加入队列。这时候，为了保证队列单调性，就应该把新元素与队尾元素比较大小。如果比队尾元素更接近最值，那么表示这个元素既比队尾元素优，又比队尾元素的时间晚，队尾元素会在这个元素之前被移出区间。这时存储这个元素就没有必要，可以直接前移队尾指针，把队尾元素移除队列。重复执行直到队列为空或该元素不比队尾元素优，最后该元素入队。

$2$ ：向后滑动的过程中，会有旧的元素退出队列。可以记录每个元素的入队位置，根据现在的位置和队列长度计算出队首元素是否退出队列。如果退出，可以后移队头指针，将队首元素出队。重复执行直到队首元素满足要求。

具体代码详见各题目。

单调队列例题

例题 $1$ ：

P1886 滑动窗口 /【模板】单调队列

单调队列模板题，不多赘述。

此处用的是 for 循环，代码比较冗余，简洁的模板请见其他题目。

#include <bits/stdc++.h>
using namespace std;
int n,k,a[2000050],heads=0,tails=0,headb=0,tailb=0;
struct node
{int v,t;
}stb[2000050],sts[2000050];inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}int main()
{n=read();k=read();for(int i=1;i<=n;i++)a[i]=read();sts[++heads].t=1;sts[heads].v=a[1];tails++;if(k==1)printf("%d ",sts[heads].v);for(int i=2;i<=n;i++){for(int j=tails;a[i]<sts[j].v&&j>=heads;j--)tails--;sts[++tails].t=i;sts[tails].v=a[i];for(int j=heads;j<=tails&&i-sts[j].t>=k;j++)heads++;if(i>=k)printf("%d ",sts[heads].v);}printf("\n");stb[++headb].t=1;stb[headb].v=a[1];tailb++;if(k==1)printf("%d ",stb[headb].v);for(int i=2;i<=n;i++){for(int j=tailb;a[i]>stb[j].v&&j>=headb;j--)tailb--;stb[++tailb].t=i;stb[tailb].v=a[i];for(int j=headb;j<=tailb&&i-stb[j].t>=k;j++)headb++;if(i>=k)printf("%d ",stb[headb].v);}return 0;
}

例题 $2$ ：

P3088 [USACO13NOV]Crowded Cows S

如果一头奶牛 $D$ 范围内的最高奶牛都不是它的两倍，那么这头奶牛就不会拥挤。所以可以通过查询最大值来确定是否会拥挤，就转化为了滑窗最大值问题。

首先把奶牛按照 $x_i$ 升序排列，然后以 $x_i$ 为位置，$h_i$ 为值建立单调队列查询最大值，队列长度为 $D$ 。单调队列需要正着跑一遍，反着跑一遍，求出两边的最大值。

注意这里是先计算，再插入值。因为奶牛自己不会拥挤自己。

当然不这样也可以，因为奶牛自己的身高不会是自己的 $2$ 倍以上。

#include<bits/stdc++.h>
using namespace std;
struct cow
{long long h,x;
}c[300000],que[300000];
long long n,d,cnt=0;
bool book1[300000],book2[300000];
bool cmp(struct cow a,struct cow b)
{return a.x<b.x;
}int main()
{scanf("%lld%lld",&n,&d);for(long long i=0;i<n;i++)scanf("%lld%lld",&c[i].x,&c[i].h);sort(c,c+n,cmp);long long head=0,tail=0;que[++tail]=c[0];head++;for(long long i=1;i<n;i++){while(que[head].x<c[i].x-d&&head<=tail)head++;if(que[head].h>=c[i].h*2)book1[i]=1;while(que[tail].h<=c[i].h&&tail>=head)tail--;que[++tail]=c[i];}head=0;tail=0;que[++tail]=c[n-1];head++;for(long long i=n-2;i>=0;i--){while(que[head].x>c[i].x+d&&head<=tail)head++;if(que[head].h>=c[i].h*2)book2[i]=1;while(que[tail].h<=c[i].h&&tail>=head)tail--;que[++tail]=c[i];}for(long long i=0;i<n;i++)if(book1[i]&&book2[i])cnt++;printf("%lld\n",cnt);return 0;
}

例题 $3$ ：

P2698 [USACO12MAR]Flowerpot S

答案是满足单调性的。越宽的花盆，可以得到的答案就越大。反之亦然。所以可以通过二分答案来做。

验证答案时，由于需要查询最值，而花盆长度固定，可以假设花盆从左向右滑动，最后的答案是每次滑动后最大值与最小值的差的最大值，实际上就是枚举花盆的结束点。所以就转化为了滑窗最值问题，可以跑两遍单调队列。一遍跑最大值，一遍跑最小值。

把奶牛按照 $x_i$ 升序排列，然后以 $x_i$ 为位置，$y_i$ 为值建立单调队列查询最大值和最小值，队列长度为二分查找时的 $mid$ 。最后把每次滑动后最大值与最小值的差的最大值与 $D$ 比较，就能知道答案的正确性了。

注意，如果一个答案合理，那么还可以尝试更小的花盆，不能直接退出。

听说ST表也能做，但是效率绝对没有单调队列高。

#include <bits/stdc++.h>
using namespace std;
struct drop
{int x,y;
}water[100010],que[300010];
int n,d,l=1,r=99999999,ans=-1,h=0,t=0;
int maxn[1000100],minn[1000100];
bool cmp1(struct drop a,struct drop b)
{return a.x<b.x;
}bool check(int l)
{int ans=0;memset(maxn,0,sizeof(maxn));memset(minn,0,sizeof(minn));h=0;t=0;que[++h].x=water[0].y;que[++t].y=water[0].x;maxn[0]=water[0].y;for(int i=1;i<n;i++){while(que[t].x<=water[i].y&&h<=t)t--;que[++t].x=water[i].y;que[t].y=water[i].x;while(water[i].x-que[h].y>l&&h<=t)h++;maxn[i]=que[h].x;}h=0;t=0;que[++h].x=water[0].y;que[++t].y=water[0].x;minn[0]=water[0].y;for(int i=1;i<n;i++){while(que[t].x>=water[i].y&&h<=t)t--;que[++t].x=water[i].y;que[t].y=water[i].x;while(water[i].x-que[h].y>l&&h<=t)h++;minn[i]=que[h].x;}for(int i=0;i<n;i++)ans=max(ans,maxn[i]-minn[i]);return ans>=d;
}int main()
{scanf("%d%d",&n,&d);for(int i=0;i<n;i++)scanf("%d%d",&water[i].x,&water[i].y);sort(water,water+n,cmp1);while(l<r){int mid=(l+r)/2;if(check(mid))ans=mid,r=mid;else l=mid+1;}printf("%d",ans);return 0;
}

单调队列的运用

单调队列是可以用来优化DP的，可以把一部分 $O(n^2)$ 的DP优化到 $O(n)$ ，是一个非常大的优化。

当然，想使用单调队列优化DP，还是需要一定的想象力的。

例题 $4$ ：

P1725 琪露诺

很容易写出这样一个转移方程：

d p [ i ] = max ⁡ { d p [ i − j ] } + a [ i ] ( L ≤ j ≤ R ) dp[i]=\max\{dp[i-j]\}+a[i](L\le j\le R) dp[i]=max{dp[i−j]}+a[i](L≤j≤R)

如果这样子朴素转移，时间复杂度是 $O(n(L-R))$ 的，很容易超时。

我们观察到，$j$ 的取值范围 $(L\le j\le R)$ 是不变的，也就意味着可以取的 $dp[i-j]$ 的个数是不变的。又因为 $j$ 在取值范围 $(L\le j\le R)$ 中是连续自然数，所以 $dp[i-j]$ 是连续的。 $dp[i-j]$ 的取值就像一个固定长度的窗口。

$dp[i-j]$ 中，我们需要逐个递增枚举 $i$ 。那么此时 $dp[i-j]$ 的取值也会随之逐个递增，就像一个固定长度的滑动窗口。就像这样：

对这是滑动窗口的原图

而此时需要求的就是 $dp[i-j]$ 的取值中的最大值，可以使用单调队列来维护。

注意如果 $i<L$ ，证明无法跳到这个格子，可以赋值为负无穷，排除干扰。

#include <bits/stdc++.h>
using namespace std;
int n,l,r,a[2000050],f[2000050],head=0,tail=0,ans=-99999999;
struct node
{int t,v;
}que[2000050];inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}int main()
{n=read();l=read();r=read();for(int i=1;i<=n+1;i++)a[i]=read();que[++tail].t=1;que[tail].v=a[1];head++;f[1]=a[1];for(int i=2;i<=n+r+1;i++){f[i]=-99999999;if(i>l){while(que[tail].v<=f[i-l]&&tail>=head)tail--;que[++tail].t=i-l;que[tail].v=f[i-l];while(que[head].t<i-r&&head<=tail)head++;f[i]=que[head].v+a[i];}}for(int i=n+1;i<=n+r+1;i++)ans=max(ans,f[i]);printf("%d",ans);return 0;
}

例题 $5$ ：

P2034 选择数字

双倍经验

P2627 [USACO11OPEN]Mowing the Lawn G

正着DP不好想，不如正难则反，要使选出的数字的和最大，就是要不选的数字和最小。

很容易写出这样一个逆向DP的转移方程：

d p [ i ] = min ⁡ { d p [ i − j ] } + a [ i ] ( 0 < j ≤ k ) dp[i]=\min\{dp[i-j]\}+a[i](0\lt j\le k) dp[i]=min{dp[i−j]}+a[i](0<j≤k)

依据例题 $4$ 的分析，这个式子也可以用单调队列来维护 min ⁡ { d p [ i − j ] } \min\{dp[i-j]\} min{dp[i−j]} ，把时间复杂度降为 $O(n)$ 。

P2034

#include <bits/stdc++.h>
using namespace std;
long long n,k,a[2000050],f[2000050],head=0,tail=0,ans=99999999999999,tol=0;
struct node
{long long t,v;
}que[2000050];inline long long read()
{long long x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}int main()
{n=read();k=read();for(long long i=0;i<n;i++){a[i]=read();tol+=a[i];}que[++tail].t=0;que[tail].v=a[0];head++;f[0]=a[0];for(long long i=1;i<n;i++){if(i-k-1>=0){while(que[head].t<i-k-1&&head<=tail)head++;f[i]=que[head].v;}f[i]+=a[i];while(que[tail].v>f[i]&&head<=tail)tail--;que[++tail].v=f[i];que[tail].t=i;}for(long long i=n-k-1;i<n;i++)ans=min(f[i],ans);printf("%lld",tol-ans);return 0;
}

P2627

#include <bits/stdc++.h>
using namespace std;
long long n,k,a[2000050],f[2000050],head=0,tail=0,ans=99999999999999,tol=0;
struct node
{long long t,v;
}que[2000050];inline long long read()
{long long x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}int main()
{n=read();k=read();for(long long i=0;i<n;i++){a[i]=read();tol+=a[i];}que[++tail].t=0;que[tail].v=a[0];head++;f[0]=a[0];for(long long i=1;i<n;i++){if(i-k-1>=0){while(que[head].t<i-k-1&&head<=tail)head++;f[i]=que[head].v;}f[i]+=a[i];while(que[tail].v>f[i]&&head<=tail)tail--;que[++tail].v=f[i];que[tail].t=i;}for(long long i=n-k-1;i<n;i++)ans=min(f[i],ans);printf("%lld",tol-ans);return 0;
}

后记

单调队列还是很需要想象力的，否则没有那么好理解。

顺便纪念一下，这是我农历虎年的最后一篇博客！