P2659 美丽的序列 (单调栈)

题目链接

Solution

直接考虑单调栈处理出每一个点作为最小值的区间长度.

然后 \(O(n)\) 找一遍最大值即可. 记得开 long long,以及要注意 \(0\) 的问题.

Code

#include<bits/stdc++.h>

#define ll long long

#define N 2000001

#define in(x) x=read()

using namespace std;

ll n,a[N];

ll L[N],R[N],sta[N],top;

ll read()

{

    char ch=getchar();ll f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

int main()

{

    in(n);

    for(ll i=1;i<=n;i++) in(a[i]);

    for(ll i=1;i<=n;i++)

    {

        if(a[i]==0){L[i]=i;continue;}

        if(a[sta[top]]<a[i]){sta[++top]=i,L[i]=i-1;continue;}

        while(a[sta[top]]>=a[i])top--;

        L[i]=sta[top]; sta[++top]=i;

    }top=0;

    for(ll i=n;i>=1;i--)

    {

      if(a[i]==0){R[i]=i;continue;}

      if(a[sta[top]]<a[i]){sta[++top]=i,R[i]=i+1;continue;}

      while(a[sta[top]]>=a[i])top--;

      R[i]=sta[top]; if(top==0)R[i]=n+1;

      sta[++top]=i;

    }

    ll ans=0;

    for(ll i=1;i<=n;i++)

    //cout<<L[i]<<' '<<R[i]<<endl;

    ans=max(ans,a[i]*(R[i]-L[i]-1));

    cout<<ans<<endl;

}

巴特西

P2659 美丽的序列 (单调栈)

题目链接

Solution

Code

最新文章

热门文章