题目描述

给定一个0-index的数组st，求出所有连续子数组的力量。
力量的定义：连续数组中的最小值 $\cdot$ 这段数组的和
最后需要求出所有连续自取件的力量之和并模1e9+7

样例

strength = {1,2,3}
{1}的力量是1*1 = 1
{2}的力量是2*2 = 4
{3}的力量是3*3 = 9
{1,2}的力量是1*3 = 3
{2,3}的力量是2*5 = 10
{1,2,3}的力量是1*6 = 6
所有连续自区间力量之和是33

算法1

(前缀和+单调站) $O(n)$

正如lee215的讨论里说的，遇到一个最值负责一个连续子数组的问题，我们可以联想到使用单调栈来解题。而当遇到连续子数组区间和的时候，我们肯能会寄希望于用前缀和来节省时间。这题很恐怖，用到了他们俩，当时想的十分头疼。

首先我看到“最小值”，“一个连续区间”这两个关键字后，很快就想到了单调栈，因为他和 Leetcode84题 拥有类似的性质。

但是求所有包含这个最小值q，并且整个区间的最小值就是q的所有区间的和就非常的恶心了，当时我想了好久都卡在这里。这里我非常推荐去看一下quantuminfo的那个推到过程。大致是这样的：
现在我们通过单调栈知道了在[l+1, … i, … r-1] 这个连续区间里st[i]是最小值。我们需要计算所有包含i的连续区间的和。在加上[a,b]的和是prefix[b] - prefix[a-1]。我们可以这么看就是我需要加的前缀和有$prefix[i] + prefix[i+1] + … prefix[r-1]$他们一共出现了i-(l+1)+1=i-l次。同理需要减去的前缀和有$prefix[l]+prefix[l+1]+…prefix[i]$并且他们出现了r-i次。所以为了快速计算这些项，我们要计算前缀和的和。

时间复杂度

参考文献

lee215的代码
quantuminfo对于区间和的讨论

C++ 代码

int totalStrength(vector<int>& st) {
    int n = st.size();
    vector<int> prefixSS(n+2, 0);
    long long ac = 0;
    int mod = 1e9+7;
    // 求出输入数据的前缀和的前缀和（这个是解决区间和的关键）
    for(int i = 0; i < n; i++){
        ac += st[i];
        prefixSS[i+1] = ((long long)prefixSS[i] + ac) % mod;
    }
    stack<int> stk; int res = 0;
    for(int i = 0; i <= n; i++){
        while(stk.size() && (i == n || st[stk.top()] > st[i])){
            int m = stk.top(); stk.pop();
            int l = stk.empty() ? -1 : stk.top();
            int accl = l < 0 ? prefixSS[m] : prefixSS[m] - prefixSS[l];
            int accr = prefixSS[i] - prefixSS[m];
            // 这里也很关键，本题解会讲一下我结合quantuminfo的文章的理解，那片文章讲的很细致        
            res = (res + ((long long)accr * (m - l) - (long long)accl * (i - m)) % mod * st[m] % mod) % mod;
        }
        stk.push(i);
    }
    return res;
}