题链

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int n,a[N],top,stk[N],ans,f1[N],f2[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]>a[i])top--;
        int x=stk[top];
        f1[i]=f1[x]+(i-x)*a[i];
        stk[++top]=i;
    }
    top=0;
    stk[0]=n+1;
    for(int i=n;i>=1;i--){
        while(top&&a[stk[top]]>a[i])top--;
        int x=stk[top];
        f2[i]=f2[x]+(x-i)*a[i];
        stk[++top]=i;
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,f1[i]+f2[i]-a[i]);
    }
    int u=0;
    for(int i=1;i<=n;i++){
        if(ans==f1[i]+f2[i]-a[i]){
            u=i;
            break;
        }
    }
    int i,ma;
    i=u;
    ma=ans;
    while(i--){
        if(a[i]>ma)a[i]=ma;
        ma=a[i];
    }
    i=u;
    ma=ans;
    while(i++<=n){
        if(a[i]>ma)a[i]=ma;
        ma=a[i];
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}