Solution
双指针做法。
本文中合法子段指一段高度 \(\ge k\) 的连续堆。
观察数据范围，发现 \(O(nm)\) 可过。于是考虑对于每个 \(k\) 都 \(O(n)\) 做一遍。
看到最长子段问题，尝试双指针。设以 \(l\) 为左端点的最长合法子段右端点为 \(r\)。易证 \(l\) 递增时 \(r\) 单调不降。
于是只需要 \(O(1)\) 判断一个区间 \([l,r]\) 是否合法。显然贪心地把左右两边所有木块尽量往这个区间上集中。设 \(pre_i\) 为第 \(1\sim i\) 堆最多能向 \(i+1\) 贡献多少个木块，\(suf_i\) 同理。\(pre,suf\) 均可以 \(O(n)\) 递推处理。
此时 \([l,r]\) 合法等价于 \(pre_{l-1}+suf_{r+1}+\sum_{i=l}^r a_i\le k\cdot (r-l+1)\)。可以 \(O(1)\) 判断。
时间复杂度 \(O(nm)\)。
Code
#include <bits/stdc++.h>
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define int long long
using namespace std;
const int N=1e6+5;
int a[N],s[N],pre[N],suf[N],n,m,k,ans;
bool check(int l,int r){return pre[l-1]+suf[r+1]+s[r]-s[l-1]>=k*(r-l+1);
}
signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m;rept(i,1,n) cin>>a[i],s[i]=s[i-1]+a[i];while(m--){ans=0;cin>>k;rept(i,1,n) pre[i]=max(0ll,a[i]+pre[i-1]-k);pert(i,n,1) suf[i]=max(0ll,a[i]+suf[i+1]-k);for(int l=1,r=0;l<=n;++l){while(r<n&&check(l,r+1)) ++r;ans=max(ans,r-l+1);}cout<<ans<<' ';}return 0;
}