bzoj2086【Poi2010】Blocks

时间：2022-09-27 19:36:50

因为long long还有PE的事WA了一下午TAT

考虑一段可行区间的平均值肯定>=k

也就是说将每个数减去k以后，一段可行区间的和非负，求一段最长区间。

一段区间的和肯定是两个前缀和的差

先求出前缀和，考虑要想让答案更优，被减数应该靠后而且大，减数应该靠前而且小

so维护两个单调队列然后two-pointers扫一遍就好了QwQ~

记得输出行末必须换行&不能有空格

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#define int long long

using namespace std;

const int Mx=;

struct Node { int val,num; } stk1[Mx],stk2[Mx];

int n,m,cnt1,cnt2,c[Mx],num[Mx],sum[Mx];

void solve(int k)

{

    cnt1=,cnt2=;

    memset(stk1,,sizeof(stk1));

    memset(stk2,,sizeof(stk2));

    int tmp=-898892147483647LL,ans=;

    for(int i=;i<=n;i++) num[i]=c[i]-k;

    for(int i=;i<=n;i++) sum[i]=sum[i-]+num[i];

    for(int i=n;i>=;i--) if(sum[i]>tmp) stk1[++cnt1].val=sum[i],stk1[cnt1].num=i,tmp=sum[i];

    tmp=2147889998483647LL;

    for(int i=;i<=n;i++) if(sum[i]<tmp) stk2[++cnt2].val=sum[i],stk2[cnt2].num=i,tmp=sum[i];

    for(int st=cnt1,to=;st>=&&to<=cnt2;st--)

    {

        while()

        {

            if(stk1[st].val-stk2[to].val>=)

            {

                ans=max(ans,stk1[st].num-stk2[to].num);

                break;

            }

            else to++;

        }

    }

    printf("%lld",ans);

}

signed main()

{

    //freopen("1.in","r",stdin);

    scanf("%lld%lld",&n,&m);

    for(int i=;i<=n;i++) scanf("%lld",&c[i]);

    while(m--)

    {

        int k;scanf("%lld",&k);

        solve(k);

        if(m)printf(" ");

        else puts("");

    }

    return ;

}

相关文章