CF【1313C2】单调栈+魔改前缀和

题意
给出n个数，第i个数为a[i]，要找到一个单峰序列b，其中b[i]<=a[i]，要使其和最大，输出序列之和最大情况下的b序列。
题解
对于a[i]用单调栈找一下它左边第一个小于它的数(记为l[i])和它右边第一个小于它的数(记为r[i])，然后分别统计一下左边的前缀和和右边的前缀和(此时的前缀和公式应该是suml[i] = sum[l[i]] + a[i] * (i - l[i]))，然后枚举一下最高点统计答案。
代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e5 + 5;
ll n, t, m, h, ans, k, a[maxn], l[maxn], r[maxn], suml[maxn], sumr[maxn], res[maxn], s[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(ll i = 1; i <= n; i++) cin >> a[i];
    for(ll i = 1; i <= n; i++){
        while(t && a[s[t]] >= a[i]) t--;
        if(t) l[i] = s[t];
        s[++t] = i;
    }
    memset(s, 0, sizeof(s)); t = 0;
    for(ll i = n; i >= 1; i--){
        while(t && a[s[t]] >= a[i]) t--;
        if(t) r[i] = s[t];
        else r[i] = n + 1;
        s[++t] = i;
    }
    for(ll i = 1; i <= n; i++) suml[i] = suml[l[i]] + (i - l[i]) * a[i];
    for(ll i = n; i >= 1; i--) sumr[i] = sumr[r[i]] + (r[i] - i) * a[i];
    for(ll i = 1; i <= n; i++) if(ans < suml[i] + sumr[i] - a[i]) ans = suml[i] + sumr[i] - a[i], k = i;
    res[k] = a[k], m = a[k], h = a[k];
    for(ll i = k - 1; i >= 1; i--){
        if(a[i] > m) res[i] = m;
        else res[i] = a[i], m = a[i];
    }
    for(ll i = k + 1; i <= n; i++){
        if(a[i] > h) res[i] = h;
        else res[i] = a[i], h = a[i];
    }
    for(ll i = 1; i <= n; i++) cout << res[i] << " ";
    cout << endl;

    return 0;
}