求区间最小值之和

动态规划+单调栈

我们定义 \(f_i\) 为所有以 \(i\) 为右端点的区间的最小值之和，用单调栈的方法来寻找左边最远的距离，使得区间内 \(A_i\) 是最小值。假设用单调栈找到了左边第一个比 \(A_i\) 小的数是 \(A_j\) ，那么 \(f_i\) 就可以加上 \((i - j) * A_i\) ，因为 \(A_j\) 往右都是 \(A_i\) 最小。而 \(A_j\) 往左的这些区间最小值等价于直接以 \(A_j\) 为右端点的最小值，因为 \(A_j\) 往右的数都比它大，没有影响，所以 \(f_i\) 再加上 \(f_j\) 就行了。
\(\sum_{i=1}^{n} f_i\)即为答案。

for (int i = 1; i <= n; i ++ )
{
    while (top && a[i] <= a[stk[top]]) top -- ;
    stk[ ++ top] = i;
    f[i] += (i - stk[top - 1]) * a[i] + f[stk[top - 1]];
}