P3594题解
题目描述
给定一个长度为 $n$ 的序列，你有一次机会选中一段连续的长度不超过 $d$ 的区间，将里面所有数字全部修改为 $0$。请找到最长的一段连续区间，使得该区间内所有数字之和不超过 $p$。
题解
根据贪心的思想，因为数字之和不超过 $p$，且希望选择的长度尽量长，显然选择的数因为尽量小。又因为数值为正数，因此将一个数变为$0$，显然是优的，因此可以将不超过 $d$ 转化为 $d$。我们不难发现，答案区间一定是包含 $d$ 的。
我们用单调队列维护答案区间，统计时减去区间类长度为 $d$ 的权值最大区间，这个可以用单调队列线性维护，用st表会MLE，线段树会TLE。
以下给出线段树O2的实现：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+100;
int n,p,d,a[N],qz[N],tree[N*4],sum,L=1,ans=INT_MIN,w[N];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x]=max(tree[x*2],tree[x*2+1]);
return;
}
void build(int l,int r,int x)
{
if(l==r)
{
tree[x]=w[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x];
}
int sum=0;
if(lson(l,r)>=l1)
sum=max(sum,get(l,lson(l,r),x*2,l1,r1));
if(rson(l,r)<=r1)
sum=max(sum,get(rson(l,r),r,x*2+1,l1,r1));
return sum;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>p>>d;
for(int i=1;i<=n;i++)
{
cin>>a[i];
qz[i]=qz[i-1]+a[i];
}
for(int i=d;i<=n;i++)
{
w[i]=qz[i]-qz[i-d];
}
build(1,n,1);
for(int i=1;i<d;i++)
{
sum+=a[i];
}
for(int i=d;i<=n;i++)
{
sum+=a[i];
int rs=sum-get(1,n,1,L+d-1,i);
while(rs>p)
{
sum-=a[L++];
rs=sum-get(1,n,1,L+d-1,i);
}
ans=max(ans,i-L+1);
}
cout<<ans;
return 0;
}