Description

给定一个长度为$n$的数组$a$，求该数组中所有子数组的最小值之和。

Constraints

• $1\le n\le 3\cdot {10}^4$
• $1\le a_i\le 3\cdot {10}^4$

Solution

假设你知道每个最小值$a_i=min\mathrm{\_}v$所覆盖的区间范围$[lo,hi]$，那么可以通过组合数得知子答案：$sub\mathrm{\_}an{s}_i=(i-lo+1)\ast (hi-i+1)\ast min\mathrm{\_}v$。

然后通过子答案之和就可以得到答案：$ans=\sum _{i=0}^{n}sub\mathrm{\_}an{s}_i$。

而最小值的覆盖范围可以通过单调栈得出。

Code

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        long ans = 0;
        constexpr long MOD = 1e9 + 7;
        // {leftmost, min_index, min_v}
        stack<tuple<size_t, size_t, int>> stk;
        auto cal = [MOD](size_t l, size_t i, size_t r, int v) {
            long llen = i - l + 1;
            long rlen = r - i + 1;
            return llen * rlen * v % MOD;
        };
        for(size_t i = 0; i < arr.size(); ++i) {
            auto v = arr[i];
            auto leftmost = i;
            while(!stk.empty() && v < get<2>(stk.top())) {
                auto [tleft, tidx, tv] = stk.top();
                stk.pop();
                ans += cal(tleft, tidx, i-1, tv);
                ans %= MOD;
                leftmost = tleft;
            }
            stk.emplace(leftmost, i, v);
        }
        while(!stk.empty()) {
            auto [l, i, v] = stk.top();
            stk.pop();
            ans += cal(l, i, arr.size()-1, v);
            ans %= MOD;
        }
        return ans;
    }
};

Link

LeetCode-907 Sum of Subarray Minimums