题面
思路
可以发现其实就是询问一个最长的区间，使得这个区间的平均数大于等于k。所以将区间内所有数字减去k，然后做一遍前缀和。只要是前缀和之差大于等于0的区间。就是满足条件的。
所以现在问题就成了对于前缀和上的每个数字，找到一个最靠前的比他小的数字。
这个可以用单调栈。可以发现如果后面的数字比前面的某个数字大，那么后面这个数字肯定不能作为左端点。所以先往单调栈里面加入一个递减序列。只有这个序列里的数字可以作为左端点。然后倒序枚举右端点。当右端点比单调栈里的数字大时，就弹出栈顶，不能继续弹出时统计答案。
/*
* @Author: wxyww
* @Date: 2019-01-19 21:29:18
* @Last Modified time: 2019-01-19 21:53:01
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 1000000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll a[N],sum[N];
int sta[N],top;
int main() {
int n = read(),m = read();
for(int i = 1;i <= n;++i) a[i] = read();
while(m--) {
ll k = read();
int ans = 0;
top = 0;
for(int i = 1;i <= n;++i) {
sum[i] = sum[i - 1] + a[i] - k;
if(sum[i] < sum[sta[top]]) {
// printf("%lld ",sum[i]);
sta[++top] = i;
}
// printf("%d ",sum[i]);
}
// printf("top:%d
",top);
sta[top + 1] = N;
for(int i = n;i >= 1; --i) {
while(sum[i] >= sum[sta[top-1]] && top) top--;
ans = max(ans,i - sta[top]);
}
printf("%d
",ans);
}
return 0;
}
/*
5 6
1 2 1 1 5
1 2 3 4 5 6
*/