因为long long还有PE的事WA了一下午TAT
考虑一段可行区间的平均值肯定>=k
也就是说将每个数减去k以后,一段可行区间的和非负,求一段最长区间。
一段区间的和肯定是两个前缀和的差
先求出前缀和,考虑要想让答案更优,被减数应该靠后而且大,减数应该靠前而且小
so维护两个单调队列然后two-pointers扫一遍就好了QwQ~
记得输出行末必须换行&不能有空格
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int Mx=;
struct Node { int val,num; } stk1[Mx],stk2[Mx];
int n,m,cnt1,cnt2,c[Mx],num[Mx],sum[Mx];
void solve(int k)
{
cnt1=,cnt2=;
memset(stk1,,sizeof(stk1));
memset(stk2,,sizeof(stk2));
int tmp=-898892147483647LL,ans=;
for(int i=;i<=n;i++) num[i]=c[i]-k;
for(int i=;i<=n;i++) sum[i]=sum[i-]+num[i];
for(int i=n;i>=;i--) if(sum[i]>tmp) stk1[++cnt1].val=sum[i],stk1[cnt1].num=i,tmp=sum[i];
tmp=2147889998483647LL;
for(int i=;i<=n;i++) if(sum[i]<tmp) stk2[++cnt2].val=sum[i],stk2[cnt2].num=i,tmp=sum[i];
for(int st=cnt1,to=;st>=&&to<=cnt2;st--)
{
while()
{
if(stk1[st].val-stk2[to].val>=)
{
ans=max(ans,stk1[st].num-stk2[to].num);
break;
}
else to++;
}
}
printf("%lld",ans);
}
signed main()
{
//freopen("1.in","r",stdin);
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++) scanf("%lld",&c[i]);
while(m--)
{
int k;scanf("%lld",&k);
solve(k);
if(m)printf(" ");
else puts("");
}
return ;
}