Solution
双指针做法。
本文中合法子段指一段高度≥k\ge k≥k的连续堆。
观察数据范围，发现O(nm)O(nm)O(nm)可过。于是考虑对于每个kkk都O(n)O(n)O(n)做一遍。
看到最长子段问题，尝试双指针。设以lll为左端点的最长合法子段右端点为rrr。易证lll递增时rrr单调不降。
于是只需要O(1)O(1)O(1)判断一个区间[l,r][l,r][l,r]是否合法。显然贪心地把左右两边所有木块尽量往这个区间上集中。设preipre_iprei为第1∼i1\sim i1∼i堆最多能向i+1i+1i+1贡献多少个木块，sufisuf_isufi同理。pre,sufpre,sufpre,suf均可以O(n)O(n)O(n)递推处理。
此时[l,r][l,r][l,r]合法等价于prel−1+sufr+1+∑i=lrai≤k⋅(r−l+1)pre_{l-1}+suf_{r+1}+\sum_{i=l}^r a_i\le k\cdot (r-l+1)prel−1+sufr+1+∑i=lrai≤k⋅(r−l+1)。可以O(1)O(1)O(1)判断。
时间复杂度O(nm)O(nm)O(nm)。
Code
#include<bits/stdc++.h>#definerept(i,a,b)for(inti(a);i<=b;++i)#definepert(i,a,b)for(inti(a);i>=b;--i)#defineintlonglongusingnamespacestd;constintN=1e6+5;inta[N],s[N],pre[N],suf[N],n,m,k,ans;boolcheck(intl,intr){returnpre[l-1]+suf[r+1]+s[r]-s[l-1]>=k*(r-l+1);}signedmain(){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(intl=1,r=0;l<=n;++l){while(r<n&&check(l,r+1))++r;ans=max(ans,r-l+1);}cout<<ans<<' ';}return0;}
