代码简单但是可以打出骚操作的数据结构
单调队列 学习笔记
什么是单调队列
单调队列是一种队中元素单调递增或者递减的元素。单调队列包括两个限定条件：大小和时间。也就是说，队中元素除了大小要单调之外，也会有一定的时间（即数组的下标）限制，超时的元素不能存在在队列中（不过有的题目没有对于时间的限制）。
单调队列的实现
单调队列是一种很活的数据结构，但实现这种数据结构无非需要两步：
踢出队首元素
把超时的队首元素从队列中踢出去。
while (q[head]<i-w+1) head++;
补进队尾元素
这里以维护单调递增队列为例。
while (head<=tail && a[q[tail]]>a[i]) tail--;
备注
这样的语句不是固定的，针对不同的题目可以做不同的修改。
单调队列例题
luogu1886 滑动窗口
先上一道板子。
把这个意象一下，就是一个数据流在流动，然后窗口是固定的。然后可以在窗口内分别维护单调递增和单调递减的序列。
具体看代码注释。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int head,tail,q[1000005],ansmin[1000005],ansmax[1000005],a[1000005],n,w;
int read()
{
char c;int r;int f=1;
c=getchar();
if (c=='-') f=-1;
while (c<'0' || c>'9')
{
c=getchar();
if (c=='-') f=-1;
}
r=0;
while (c>='0' && c<='9')
{
r=r*10+c-'0';
c=getchar();
}
r*=f;
return r;
}
void getmax()
{
memset(q,0,sizeof(q));
head=1;tail=1;
ansmax[1]=a[1];
q[head]=1;
for (int i=2;i<=n;i++)
{
while (q[head]<=i-w && q[head]!=0) head++;//当前队首不在滑动窗口里面，出队
while (head<=tail && a[q[tail]]<a[i]) tail--;//如果当前队尾比i小,出队
q[++tail]=i;//i入队
ansmax[i]=a[q[head]];
//因为此时的队列已经维护完毕，只剩下比i大而且没过期的了，而且队首肯定是最大的，不然早被踢掉了
}
}
void getmin()
{
memset(q,0,sizeof(q));
head=1;tail=1;
ansmin[1]=a[1];
q[tail]=1;//点1入队
for (int i=2;i<=n;i++)
{
while (q[head]<=i-w && q[head]!=0) head++;//当前队首不在滑动窗口里面，出队
while (head<=tail && a[q[tail]]>a[i]) tail--;//如果当前队尾比i大,出队
q[++tail]=i;//i入队
ansmin[i]=a[q[head]];
//因为此时的队列已经维护完毕，只剩下比i小而且没过期的了，而且队首肯定是最小的，不然早被踢掉了
}
}
int main()
{
n=read();w=read();
for (int i=1;i<=n;i++) a[i]=read();
getmin();
getmax();
for (int i=w;i<=n;i++) printf("%d ",ansmin[i]);
printf("\n");
for (int i=w;i<=n;i++) printf("%d ",ansmax[i]);
printf("\n");
}
luogu1714 切蛋糕
一道水题，然而花了我好半天。
一开始的漏洞思维不想多说，说一下正解。
这个题就是找一对前缀和，然后让这对前缀和的差最大就好了。但是这对前缀和要在一定的范围内，而且队列里面的前缀和显然是越小越好，所以比起当前的，又老又大的直接踢掉就行了。所以维护一个单调递增序列就能实现了。
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#define rint register int
using namespace std;
int n,m,sum[1000100],f[1000100],ans=-2100000000;
int q[1000010],head=1,tail=0;
int main(){
cin>>n>>m;
for (rint i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
sum[i]=sum[i-1]+a;
}
for (rint i=1;i<=n;i++)
{
while (q[head]<=i-m) head++;
ans=max(ans,sum[i]-sum[q[head]]);
while (sum[q[tail]]>sum[i] && head<=tail) tail--;
q[++tail]=i;
}
printf("%d\n",ans);
}
luogu2629 好消息，坏消息
这个题最难的一点就是想到破环为链。
想到之后其实很好办，先求出前缀和，单调队列的时间限制就是某个点的前n个。因为假如序列为a,b,c,d,e，那么以c为第一个点，老板的怒气值序列就是c,c+d,c+d+e,c+d+e+a,c+d+e+a+b。在这个怒气值序列中最小的那个还大于0就说明这种情况成立，但由于求的是前缀和，所以还要减去当前点前面那些店的前缀和再和0比较。维护一个单调递增序列就可以搞定。
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
int n,a[2000002],ans,q[2000002],s[2000002],head=1,tail=0;
int main()
{
scanf("%d",&n);
for (rint i=1;i<=n;i++)
{
scanf("%d",&s[i]);
a[i]=a[i-1]+s[i];
}
for (rint i=n+1;i<=2*n;i++) a[i]=a[i-1]+s[i-n];
for (rint i=1;i<=2*n;i++)
{
while (q[head]<i-n && head<=tail) head++;
while (a[q[tail]]>a[i] && head<=tail) tail--;
q[++tail]=i;
if (i>n) if (a[q[head]]-a[i-n-1]>=0) ans++;
}
printf("%d",ans);
}
luogu2422 良好的感觉
这题说实话想了我差不多一个小时。第一次没看题解用单调队列来优化DP。
这个题的单调队列很明显是一个没有时间限制的，所以只需要考虑队中元素是什么的问题。我们可以注意到，这个题的数据范围规定没有负数，所以前缀和绝对是会越来越大的，所以队中元素应该是那个最不舒服的值。
然后转念想一想，如果这题是一个数据小的普通DP怎么做？那就是找到每个点左边那个比它小的，以及右边那个比它小的。这左右边界之间的，就是这个点最多能管到的范围。对于单调队列来说，我们可以维护一个单调递增的队列，然后往外踢的时候，被踢掉的点就找到了“右边那个比它小的”，维护完队列之后，队列中位于当前元素前一个的那个元素就是“左边那个比它小的”。这样就可以计算某个点能管到的范围了，最后再乘以这个点本身的值，比较出最大值就好了。
当然还有一个问题，如果某个点一直没有被踢掉怎么办？好办，在序列的最后加一个值为0的元素，就可以在最后一次循环踢掉所有队中元素，完成最后的处理。
PS：其实这题的数据结构严格来说叫做单调栈。
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
long long n,a[100001],q[100001],sum[100001],f[100001],ans,tail;
int main()
{
scanf("%lld",&n);
for (rint i=1;i<=n;i++) scanf("%lld",&a[i]);
n++;a[n]=0;
for (rint i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
while (a[q[tail]]>a[i])
{
f[q[tail]]+=(sum[i-1]-sum[q[tail]]);
tail--;
}
f[i]=sum[i]-sum[q[tail]];
q[++tail]=i;
}
for (rint i=1;i<=n-1;i++) ans=max(ans,f[i]*a[i]);
printf("%lld",ans);
}
luogu3522 TEM
P1
这个题代码难度简单，但是极其难想。想了我整整一个两个多小时都想不明白，看了题解还没明白，又让ASIA大佬讲了一遍还是没明白，一直到现在都没明白，所以手打思路整理一下。
先看懂代码，原理自然就出来了。
先看队头的操作
while(head<=tail && l[q[head]]>r[i]) head++;
这个倒是好理解，如果队头的最小温度大于当前的最大温度，那么就把这个队头踢出去，因为队头无法一直推到现在，对于当前点之后的点，也无法由队头推过来，所以这个队头已经没用了，直接踢掉就行了。
再看队尾的操作
while(head<=tail && l[q[tail]]<l[i]) tail--;
这个就难以理解了。这个玩意似乎是在维护一个最小温度单调递减的序列。ASIA大佬讲了半天我都没有听懂，但是至少懂了一句，就是队列中的最小温度越大，对后面的限制也就越大。
P2
又让ASIA大佬从头讲了一遍，终于明白了。
明白的前提是知道自己之前不明白在哪里。之前我不理解队尾为什么这样操作的原因就是不知道队列中的元素为什么是连续的。换而言之，如果队列中的元素能够保证是连续的，就很好理解了，首先队头的最小值是队列中最大的，根据木桶原理，这个队头显然是当前元素能否入队的限制。然后之前的队头操作可以保证当前队头和队列中的每个元素都是有交集的，所以只要满足队头元素的限制，就能满足队列中所有元素的限制，也就可以入队，也就是说队列可以一道推下来，而队头的操作能够保证队中可能不降。
那么接下来解决为什么这个队列是连续的，因为如果有一个使队列不连续的点要入队，但是这个点后面的点如果想要从这个点之前的点推过来就必须选上这个点，所以如果这个点比起前面那个点是绝对下降的关系，由于队列的单减性，所以这个点比起队列中所有的点都是绝对下降，也就是说都没有交集，在队头操作就可以直接把队列中的都踢掉，那就会直接另起炉灶。所以只要有一个不连续的就会另起炉灶，队列中的元素完全是连续的。
综上所述，这个单调队列的“时间限制”，也就是“条件限制”，就是“有交集”。这个单调队列就是一个连续的，保证每个元素都有交集的单调递减队列。
为什么是单调递减？因为如果把这个递减队列中的一个元素改成增的，那么后面的元素想选它前面的元素就必须选它，所以它前面那些“限制值”比它低的，就可以说再见了。
终于啰嗦完了，上代码。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rint register int
using namespace std;
int q[1000005],l[1000005],r[1000005],n,m,ans,head=1,tail;
int main()
{
cin>>n;
for(rint i=1;i<=n;i++) cin>>l[i]>>r[i];
for(rint i=1;i<=n;i++)
{
while(head<=tail && l[q[head]]>r[i]) head++;
while(head<=tail && l[q[tail]]<=l[i]) tail--;
q[++tail]=i;
ans=max(ans,i-q[head-1]);
}
cout<<ans;
}
luogu3572 Little Bird
这个题没有翻译，先上个翻译
有一排n棵树，第i棵树的高度是Di。
有一些ZSH要从第一棵树到第n棵树去找他的妹子玩。
如果ZSH在第i棵树，那么他可以跳到第i+1,i+2,…,i+k棵树。
如果ZSH跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。
为了有体力和妹子玩，ZSH要最小化劳累值。
输入描述：
第一行输入有n棵树；
第二行输入这n棵数的高度；
第三行输入有p个ZSH；
第4~p+3行输入这个ZSH可以跳多远；
输出描述：
共p行，每一行输出一个ZSH的劳累值。
样例输入：
9
4 6 3 6 3 7 2 6 5
2
2 5
样例输出：
2
1
裸的DP很好推，f[i]=max(f[i],f[j]+(d[j]<=d[i]));
单调队列优化DP可以实现，具体代码有注释。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,d[1000001],f[1000001],q[1000001],k,p,jump,head,tail;
int main()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>d[i];
cin>>p;
for (int k=1;k<=p;k++)
{
cin>>jump;
memset(f,0,sizeof(f));
q[1]=1;
head=1;tail=1;
for (int i=2;i<=n;i++)
{
while (head<=tail && q[head]+jump<i/*队首跳不到当前点*/) head++;
f[i]=f[q[head]]/*队首元素的疲劳值*/+(d[q[head]]<=d[i]);//往高处跳疲劳值+1
while (head<=tail && (f[q[tail]]>f[i] || (f[q[tail]]==f[i] && d[q[tail]]<=d[i]))) tail--;
//队尾元素的疲劳值大于新达到的点,或者疲劳值相等的同时新达到的点高度更高
//那么当前队尾就没有存在价值了
q[++tail]=i;
}
cout<<f[n]<<endl;
}
}
luogu3957 跳房子
这题第一遍看错题了，一分没得……
如果看对了题的话拿到50分的DP分应该不难，但是这题数据毒瘤，必须要用单调队列优化才能AC。之后写单调队列又莫名写炸，和网上的dalao们好像都不是一个写法……贴一个网上dalao的做法。
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inb inline bool
#define big 1e9
using namespace std;
int n,d,k,x[500001],s[500001],q[500001],f[500001];
inb check(int g)
{
for (rint i=1;i<=n;i++) f[i]=-big;
memset(q,0,sizeof(q));
int head=1,tail=0,xmin=max(d-g,1),xmax=d+g,j=0;
for (rint i=1;i<=n;i++)
{
while (j<i && x[i]-x[j]>=xmin)
{
while (head<=tail && f[q[tail]]<f[j]) tail--;
q[++tail]=j;j++;
}//把有可能跳到当前点的格子入队
while (head<=tail && x[q[head]]+xmax<x[i]) head++;//把过期的出队
if (head>tail || f[q[head]]==-big) continue;
//如果队空或者队里全是达不到的点就说明当前点达不到
else f[i]=f[q[head]]+s[i];
if (f[i]>=k) return 1;
}
return 0;
}
int main()
{
scanf("%d%d%d",&n,&d,&k);
for (rint i=1;i<=n;i++)
scanf("%d%d",&x[i],&s[i]);
int l=0,r=x[n],ans=-1;
while (l<=r)
{
int mid=(l+r)/2;
if (check(mid))
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d",ans);
}
