BZOJ 4385 Wilcze doły

题目大意

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

首先预处理出所有长度为$d$的区间的权值和。把他们放到一个单调栈中。之后双指针扫一下，对于每一个右端点求出最靠左的左端点。

傻题，没啥特殊需要处理的。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long ll;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll ri()
{
	ll ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp-'0'),tmp=nc();
	return ret;
}
int n,d,q[2000010],l=1,r=0,ans;
ll p,sum[2000010],f[2000010];
int main()
{
	int i,j;
	n=ri(),p=ri(),d=ri();
	for(i=1;i<=n;++i) sum[i]=sum[i-1]+ri();
	for(i=1;i+d-1<=n;++i) f[i]=sum[i+d-1]-sum[i-1];
	for(i=d,j=0;i<=n;++i)
	{
		while(l<=r&&f[q[r]]<=f[i-d+1]) --r;
		q[++r]=i-d+1;
		while(sum[i]-sum[j]-f[q[l]]>p)
		{
			++j;
			while(q[l]<=j) ++l;
		}
		ans=max(ans,i-j);
	}
	printf("%d\n",ans);
	return 0;
}