思路：单调栈+数论

对于一个值$a_j$，当$a_k<a_j, a_j<a_i(k\lt j,j\lt i)$时，$a_j$对$k$~$i$间的数组都是有贡献的。

通俗的说，对于数组$[2,9,5,8,3]$，$5$仅是$2$和$3$之间的数组的最小值，其所需要贡献的连续子数组为$[9,5],[5],[5,8],[9,5,8]$。

也就是说，对于$a_j$，我们需要找到它左右两边的第一个更小的值（对于5来说是2和3）。这符合单调递增栈的特点。所以我们需要维护一个单调递增栈。

假设栈顶为$s[top]$，那么它左边的最小值就是$s[top-1]$，当一个比栈顶更小的元素$a_i$准备入栈时，那么栈顶右边第一个更小的值也就找到了。当然也可能不存在，所以我们人工在数组最后插入一个极小值$-∞$，这样就一定存在了。

那么我们如何计算栈顶对答案的贡献呢？

设:

$l=s[top]-s[top-1]$

$r=i-s[top]$

以当前栈顶为右边界的子数组，其向左(包括栈顶)长度可以是$1,2,3,...,l$，这是一个$d=1$的等差数列，其和为$suml=(1+l)*l/2$。对应子数组为$[9,5],[5]$

当然，还可以向右。由于我们已经知道了向左的长度可以是$1,2,3,...,l$，那么向右(包括栈顶)的长度就可以是$1,2,3,...,r$。对应子数组为$[5],[5,8]$

同时，我们不仅可以单向一边，还可以向两边，对应子数组为$[5],[9,5,8]$。

这之间存在重复运算。所以还需要容斥。

可以发现$[5,8]$可以看作$[5]$向右扩展而来，同样，$[9,5,8]$可以看作$[9,5]$向右扩展而来。即，向右扩展了$0,1,2,...,r-1$位。每多扩展一位，都相当于$suml+l$（左边$l$个选择，右边多一位，相当于每个选择答案都+1）。这是一个$d=l$的等差数组，其和为$(suml+suml+(r-1)*l)*r/2$。

最终栈顶的贡献为$a[s[top]]*(suml+suml+(r-1)*l)*r/2$。

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=1e5+10;
int n;
int a[maxn];
int s[maxn],top=0;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    n++;
    a[n]=INT_MIN;
    long long ans=0;
    for(int i=1;i<=n;++i){
        while(top&&a[i]<a[s[top]]){
        	int l = s[top]-s[top-1];
        	int r = i-s[top];
        	ll suml = 1ll*(1+l)*l/2;
        	ll tmp = (suml+suml+1ll*(r-1)*l)*r/2;
            ans+=a[s[top]]*(tmp);
            top--;
        }
        s[++top]=i;
    }
    cout<<ans;
    
    
    return 0;
}

题目描述

小明定义一个数组的权值为这个数组的最小值乘上数组的长度。 小明现在有一个数组，他想知道这个数组的所有连续子数组的权值之和。

输入描述

第一行输入一个整数 $n(1\le n\le 10^5)$表示数组长度。 第二行输入$n$个整数表示数组 $a_i(1\le a_i\le 10^3)$

输出描述

一个整数。

样例

输入

2
1 2

输出

5

说明

子数组[1]的权值为$1*1=1$

子数组[2]的权值为$2*1=2$

子数组[1,2]的权值为$1*2=2$。

因此所有子数组的权值之和为1+2+2=5。