Luogu P2422 A good feeling Answer key

Topic link ：P2422 A good feeling

The question ：

kkk Made a human sensory analyzer . every single day , Everyone has a feeling value $A_i$,$A_i$ The bigger it is , It means that people feel more comfortable . For a while $\left[i,j\right]$ Inside , Human comfort is defined as $\left[i,j\right]$ The feeling value of the most uncomfortable day in $\times$$\left[i,j\right]$ The sum of the feeling value of each day . Now give kkk In succession $N$ The feeling value in the sky , Excuse me, , At what time ,kkk Feel the most comfortable ？

about $100\%$ The data of ,$1\le N\le 100000$,$1\le \text{Receptive value}\le 1000000$.

To simplify the meaning of the question is

Find an interval , Multiply the minimum value of the interval by the sum of the interval

Consider the contribution of each minimum to the interval

Let the current number be $a_i$ ,

It can become the interval of the minimum $[l,r]$ Satisfy $l\in [j+1,i],r\in [i,k-1]$

among $j$ It's all $a_j<a_i$ The largest of $j$ ,$k$ It's all $a_k<a_i$ The smallest of all $k$

set up $f_i$ Before presentation $i$ The largest answer in the number
$$f_i=(f_j+S_i-S_j)+(f_k+S_{k-1}-S_i)$$
there $j,k$ Synonymous with the above ,$S_i$ Prefix and , namely $S_i={\sum }_{j=1}^i{a}_j$

So the monotone stack is used to maintain the minimum , From left to right , You can finish the left half

So what happened to the right half ？

It's not hard to find out $a_k$ It must be the first one to add to the monotone stack $a_i$ Number kicked out

We just have to kick $a_i$ When the time is right $i$ To $k-1$ Contribution to add $f_i$ On it

Be sure to put $a_{n+1}$ Set to a minimum , So that it can kick out all the front

Time complexity $O(n)$

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,top,a[N],stk[N],f[N],sum[N];
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    a[++n]=0;
    for(int i=1; i<=n; i++)
    {
    
        sum[i]=sum[i-1]+a[i];
        while(a[stk[top]]>a[i])
        {
    
            f[stk[top]]+=sum[i-1]-sum[stk[top]];
            --top;
        }
        f[i]=sum[i]-sum[stk[top]];
        stk[++top]=i;
    }
    int res=0;
    for(int i=1; i<n; i++)
        res=max(res,f[i]*a[i]);
    cout << res << '\n';
    return 0;
}

Reprint please explain the source