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\_v\)所覆盖的区间范围\([lo, hi]\)，那么可以通过组合数得知子答案：\(sub\_ans_i = (i - lo + 1) * (hi - i + 1) * min\_v\)。
然后通过子答案之和就可以得到答案：\(ans = \sum_{i=0}^{n} sub\_ans_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;
}
};