P3503 [POI 2010] KLO-Blocks
一个区间能做到高度全部 \(\ge k\)，当且仅当该区间的平均值 \(\ge k\)。
于是我们为每个 \(a_i\) 减去 \(k\)，再求出其前缀和数组 \(s\)。
问题转化为求:
\[\large
\max\limits_{l\le r,s_r-s_{l-1}\ge 0} (r-l+1)
\]
暴力可以做到 \(O(n^2)\) 的时间复杂度，考虑优化。
我们发现，若 \(i<j\)，且 \(s_i\le s_j\)，那么 \(i+1\) 作左端点一定不劣于 \(j+1\) 作左端点；同理，此时 \(j\) 作右端点一定不劣于 \(i\) 作右端点。
换句话说，我们可以规定，只有前缀最小值处才能作为 \(l-1\)，只有后缀最大值处才能作为 \(r\)。
我们可以用两个单调栈来维护这些左右端点。
根据上面的分析，可知在下标升序的情况下，所有可能的左右端点均是按 \(s\) 单减的。
另外一种方法是仅存储左端点，然后从后往前枚举右端点，显然前一种方法中参与统计的答案是此做法的子集，所以仍然是正确的。
时间复杂度均为 \(O(nm)\)。
写法 $1$ - R234517631
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,a[N],s[N],sl[N],sr[N],tl,tr;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];while(m--){int k,ans=tl=tr=0;cin>>k;for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-k;sl[++tl]=0;//l-1=0 也要算入for(int i=1;i<=n;i++) if(s[i]<s[sl[tl]]) sl[++tl]=i;for(int i=n;i;i--) if(!tr||s[i]>s[sr[tr]]) sr[++tr]=i;for(int i=1,j=tr;i<=tl;i++){for(;j&&s[sl[i]]<=s[sr[j]];j--) ans=max(ans,sr[j]-sl[i]);}cout<<ans<<" ";}return 0;
}
写法 $2$ - R234266797
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,a[N],s[N],st[N],top;//st 存储 l-1
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int k,ans;while(m--){cin>>k;ans=0;st[top=1]=0;//l-1=0 也要算入for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i]-k;if(s[i]<s[st[top]]) st[++top]=i;}for(int i=n;i;i--){while(top&&s[st[top]]<=s[i]) ans=max(ans,i-st[top--]);}cout<<ans<<" ";}return 0;
}