Blocks

时间:2021-06-25 22:09:55

Description

Blocks

solution

这题和之前做过的一题的一个套路非常类似:把不是更优的决策给去掉,使得序列变得具有单调性,分析这题:

发现如果两个右端点 \(i\),\(j\) 满足 \(sum[j]<sum[i]\) 且 \(j<i\),那么 \(j\) 是不会进入最优决策的.

同理:如果两个左端点 \(i\),\(j\) 满足 \(sum[j]<sum[i]\) 且 \(i<j\) 那么 \(i\) 是不会进入最优决策的

所以我们分别维护一个左右端点的单调栈,然后两个单调指针扫一遍答案取Max即可

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=1000005;
inline int gi(){
RG int str=0;RG char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
int n,Q,a[N],st[N],q[N],tp=0;ll sum[N]; inline void solve(ll x){
int top=0,ans=0,tp=0; q[++tp]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i]-x;
if(sum[i]<sum[q[tp]])q[++tp]=i;
}
for(int i=n;i>=1;i--){
if(!top || sum[i]>sum[st[top]])st[++top]=i;
} for(int i=1;i<=tp;i++){
while(top>1 && sum[q[i]]<=sum[st[top-1]])top--;
if(q[i]<st[top] && sum[st[top]]-sum[q[i]]>=0)
ans=Max(ans,st[top]-q[i]);
}
printf("%d ",ans);
} void work()
{
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++)a[i]=gi();
for(int i=1;i<=Q;i++)solve(gi());
} int main()
{
work();
return 0;
}