题意

给定一个长度为$n$的序列，你有一次机会选中一段连续的长度不超过$d$的区间，将里面所有数字全部修改为$0$。请找到最长的一段连续区间，使得该区间内所有数字之和不超过$p$

数据范围：$1 \le d \le n \le 2000000,0 \le p \le 10^{16}$

题解

首先能够想到枚举区间左右端点$l,r$，再减去区间内和最大的一段，用前缀和表示为$$s[r]-s[l-1]-\max(s[x]-s[x-d])$$
但这样是$O(n^3)$的
考虑将枚举$l,r$转为尺取法：固定$r$时，只有当不满足条件时将$l$右移
这样时间复杂度为$O(n^2)$，仍然不足以通过此题
发现$\max$具有单调性，考虑进行单调队列优化
时间复杂度为$O(n)$

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2000000+10;
int n,d;
LL p;
LL a[N],s[N],t[N];
int hd,tl,ans;
int mq[N];
int main(){
    scanf("%d%lld%d",&n,&p,&d);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s[i]=a[i]+s[i-1];
    }
    for(int i=d;i<=n;i++)
        t[i]=s[i]-s[i-d];
    ans=d;
    hd=1,tl=0;
    mq[++tl]=d;
    for(int l=1,r=d+1;r<=n;r++){
        for(;hd<=tl && t[r]>t[mq[tl]];tl--);
        mq[++tl]=r;
        for(;hd<=tl && s[r]-s[l-1]-t[mq[hd]]>p;){
            l++;
            for(;hd<=tl && mq[hd]-d+1<l;hd++);
        }
        ans=max(ans,r-l+1);
    }
    printf("%d",ans);
    return 0;
}