关于单调队列的一些运用 洛谷P3594

题目大意：
给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。
数据范围：n<=2e6；
题解：
我们考虑对于j作为右端点，那么这个区间的左端点在右端点递增时具有单调递增性，可以用反证法证明。那么对于每一个右端点，我们要求出它的左端点即可，那么问题就转化成了求已知右端点与上次询问的左端点，求期间的长度为d权值最大的区间，然后根据是否满足要求来更新左端点，就能求出答案。
下面是今天的核心内容：单调队列
单调队列的要求是在队列中单调递增/递减，它的作用主要是维护一段区间内的合法最值，由于它是队列，其中保存了多个较优解，当区间更改后，也不会出现没有最优解的情况。其一般用于优化其他算法，主要是dp的优化，其中一般保留坐标，用坐标来提取权值，这样有利于更好的维护队列中所存区间合法。其单调性不仅是权值上的单调性，并且有合法上的单调性，即越后入队的弹出越晚，那么就可以很方便的清除不合法的区间。
这道题就按照题目要求和单调队列要求的维护就好了；

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+10;
deque<LL>q;
inline LL read()
{
    LL ret=0;char c=getchar();
    while(c<'0'||c>'9')	c=getchar();
    while(c>='0'&&c<='9')	ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
LL n,p,d,num[maxn],sum[maxn],sec[maxn];
int main()
{
    //freopen("4385.in","r",stdin);
    //freopen("4385.out","w",stdout);
    n=read(),p=read(),d=read();
    for(int i=1;i<=n;i++)	num[i]=read();
    for(int i=1;i<=n;i++)	sum[i]=sum[i-1]+num[i];
    for(int i=d;i<=n;i++)	sec[i-d+1]=sum[i]-sum[i-d];
    q.push_front(1);LL last=1,ans=d;
    for(int i=2;i<=n-d+1;i++){
        while(!q.empty()&&sec[i]>sec[q.back()])	q.pop_back();
        q.push_back(i);
        while(!q.empty()&&last>q.front())	q.pop_front();
        while(!q.empty()&&sum[i+d-1]-sum[last-1]-sec[q.front()]>p){
            last++;
            if(!q.empty()&&last>q.front())	q.pop_front();
        }
        ans=max(ans,i+d-1-(last-1));
    }
    printf("%lld",ans);
    return 0;
}