「AGC005B」 Minimum Sum

题意

给定一个整数序列 \(a\)，求 \(\sum\limits^{N}_{l=1}\sum\limits^{N}_{r=l} \min(a_l,a_{l+1},\cdots,a_{r})\) (注意 \(r\) 的初始值是 \(l\))。

分析

当我们模拟样例时，可以发现，每一个数都只会在一个区间内最小，而最小值不断更新成更小的，所以可以用单调栈求解出 \(a_i\) 对应的 \(l_i,r_i\) 。

设栈数组为 \(st\)，栈顶为 \(top\)，若 \(a_i<a_{st_{top}}\)，把 \(r_{st_{top}}\) 更新为 \(i\)，然后弹出栈顶。最后把 \(l_i\) 更新为 \(st_{top}\)，并把 \(i\) 入栈。

最后注意有时栈内还有元素，把它们全部弹出，并把它们的 \(r\) 设为 \(n+1\)。

统计答案时，因为 \(i\) 的有效范围在 \(r_i-i\) ，\(i\) 之前有 \(i-l_i\) 个比它大的数(有效区间内)，所以 \(a_i\) 被加的次数为 \((i-l_i)\times(r_i-i)\)。

最后答案为 \(\sum\limits^{N}_{i=1}(i-l_i)\times(r_i-i)\times a_i\)。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll maxn=2e5+5;
ll n,a[maxn],ans,top=1,st[maxn],l[maxn],r[maxn];
signed main(){
    n=read();
    for(ll i=1;i<=n;++i)a[i]=read();
    for(ll i=1;i<=n;++i){
        while(a[st[top]]>a[i])r[st[top--]]=i;
        l[i]=st[top],st[++top]=i;
    }
    while(top)r[st[top--]]=n+1;
    for(ll i=1;i<=n;++i){
        ans+=(i-l[i])*(r[i]-i)*a[i];
    }
    printf("%lld",ans);
    return 0;
}