Blocks—单调栈

思路：

题目意思是求平均数>=k的最长序列
先求出a[i]-k的前缀和
就是求sum[i]-sum[j]>=0的最大i-j
当j<=k<=isum[j]<=sum[k]j<=k<=isum[j]<=sum[k]
更新i的时候，k就不如j优
所以处理出来一个单调上升的数组(stak)，那答案就在里面选
倒序更新，单调栈一直减减就好
因为如果用stak[top]更新了i，因为i是倒序枚举，递减的，stak又是上升的
所以只有top--才能更新答案

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,k,a[N],s[N],top,sum[N];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>k;
		for(int i=1;i<=n;i++) 
		    sum[i]=sum[i-1]+a[i]-k;
	    top=1;
	    s[1]=0;
	    for(int i=1;i<=n;i++)
		    if(sum[s[top]]>sum[i]) 
		        s[++top]=i;
	    int ans=0;
	    for(int i=n;i>=1;i--) {
		    while(top>1&&sum[i]>=sum[s[top-1]]) top--;
		    if(sum[s[top]]<=sum[i])
		        ans=max(ans,i-s[top]);
	    }
	    printf("%lld ",ans);
	}
	return 0;
}

博主原文来自：https://www.cnblogs.com/dsrdsr/p/10428125.html   大佬博主写的让我很明白

#一名爱玩狂铁的oier#