Description：

长度为 $n$ 的序列，选一段长度不超过 $d$ 的区间，将里面所有数字全部修改为 $0$ 。找到最长的一段连续区间数字之和不超过 $p$ 。

$1\le n \le 2\times 10^6$

Solution：

首先发现最后选的区间一定包含修改的区间，修改区间长度一定是 $d$ ，实际上就是在选出的区间中选一个权值和最大的长为 $d$ 的区间。

首先预处理前缀和和到 $i$ 这个位置截至的长度为 $d$ 的和，然后用单调队列维护滑动窗口单调区间最值，双指针分别维护区间和和单调队列，如果不合法则区间头指针右移，如果头指针越过了队头就弹队头，这样下去由于区间和 $-$ 最大值一定是单调递减的，感性理解一下就是区间和减的快，区间和减了最大值不一定减，所以这样计算出的就是当 $r=pos$ 时的区间最大值，最后不停取 $max$ 就能得到最值了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,d;

ll p;

#define MAXN 2000010

ll a[MAXN];

ll s[MAXN];

int q[MAXN],head = 1,tail = 0;

ll sumv[MAXN];

int main()

{

	scanf("%d%lld%d",&n,&p,&d);

	for(int i = 1;i <= n;++i)a[i] = read();

	ll sum = 0;

	for(int i = 1;i <= n;++i)

	{

		sumv[i] = sumv[i - 1] + a[i];

		sum = sum + a[i];

		if(i >= d)

		{

			sum -= a[i - d];

			s[i] = sum;

		}

	}

	int ans = 0;

	for(int l = 1,r = d;r <= n;++r)

	{

		while(head <= tail && s[q[tail]] <= s[r])--tail;

		q[++tail] = r;

		while(sumv[r] - sumv[l - 1] - s[q[head]] > p)

		{

			++l;

			while(head <= tail && q[head] - d + 1 < l)++head;

		}

		ans = max(ans,r - l + 1);

	}

	cout << ans << endl;

	return 0;

}