P2659 美丽的序列 [单调栈]

P2659 美丽的序列 [单调栈]

传送门

水题

#include<bits/stdc++.h>
#define N 2000050
#define LL long long
using namespace std;
int n,a[N],l[N],r[N],sta[N],top; LL ans;
int read(){int cnt=0;char ch=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}
int main(){n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++){while(top && a[sta[top]] >= a[i]) top--;if(top==0) l[i] = 0;else l[i] = sta[top];sta[++top] = i;} top=0;for(int i=n;i>=1;i--){while(top && a[sta[top]] >= a[i]) top--;if(top==0) r[i] = n+1;else r[i] = sta[top];sta[++top] = i;}for(int i=1;i<=n;i++) ans = max(ans,(LL)a[i]*(r[i]-l[i]-1));printf("%lld",ans); return 0;
}