bzoj2086: [Poi2010]Blocks DP，单调栈

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2086

思路

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

错误

边界好麻烦

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+7;
ll read() {
    ll x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll n,m,k,a[N],stak[N],top,sum[N];
void solve() {
    for(ll i=1;i<=n;++i) sum[i]=sum[i-1]+a[i]-k;
    stak[top=1]=0;
    for(ll i=1;i<=n;++i)
        if(sum[stak[top]]>sum[i]) stak[++top]=i;
    // for(ll i=1;i<=top;++i) cout<<sum[stak[i]]<<"! ";puts("");
    ll ans=0;
    for(ll i=n;i>=1;--i) {
        while(top>1&&sum[i]>=sum[stak[top-1]]) top--;
        // if(top) top++;
        // cout<<sum[i]<<" "<<sum[stak[top]]<<" !\n";
        // if(sum[i]>=sum[stak[top]]&&top)
        // cout<<stak[top]<<" "<<i<<" "<<top<<"\n";
        if(sum[stak[top]]<=sum[i])
        ans=max(ans,i-stak[top]);
    }
    printf("%lld ",ans);
}
int main() {
    // freopen("3.in","r",stdin);
    n=read(),m=read();
    for(ll i=1;i<=n;++i) a[i]=read();
    for(ll i=1;i<=m;++i) {
        k=read();
        solve();
    }
    return 0;
}