Tổng nhỏ nhất mảng con trong C++

Cho mảng A, tính tổng min(B) với B duyệt qua mọi mảng con liên tiếp của A. Kết quả modulo 10^9+7.

Ví dụ: [3,1,2,4] → Các mảng con: [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]. Min: [3,1,2,4,1,1,2,1,1,1], tổng = 17.

Giải thuật (Ngăn_stack đơn điệu)

1. Tìm left[i]: chỉ số gần nhất bên trái A[left] < A[i] (dùng stack tăng).
2. Tìm right[i]: chỉ số gần nhất bên phải A[right] <= A[i] (stack tăng, duyệt ngược).
3. Phần tử A[i] là min của (i-left[i])*(right[i]-i) mảng con.
4. Đóng góp: A[i] * (i-left[i]) * (right[i]-i).
5. Tổng tất cả, modulo 1e9+7.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;

class Solution {
public:
    lli add(lli a, lli b) { return (a % MOD + b % MOD) % MOD; }
    lli mul(lli a, lli b) { return (a % MOD * b % MOD) % MOD; }
    int sumSubarrayMins(vector<int>& A) {
        stack<int> st;
        int n = A.size();
        vector<int> left(n, -1), right(n, n);
        for(int i = 0; i < n; i++) {
            while(!st.empty() && A[st.top()] >= A[i]) st.pop();
            if(!st.empty()) left[i] = st.top();
            st.push(i);
        }
        while(!st.empty()) st.pop();
        for(int i = n-1; i >= 0; i--) {
            while(!st.empty() && A[st.top()] > A[i]) st.pop();
            if(!st.empty()) right[i] = st.top();
            st.push(i);
        }
        lli ans = 0;
        for(int i = 0; i < n; i++) {
            int leftBound = i - left[i];
            int rightBound = right[i] - i;
            ans = add(ans, mul(A[i], mul(leftBound, rightBound)));
        }
        return ans;
    }
};

int main() {
    vector<int> v = {3,1,2,4};
    Solution ob;
    cout << ob.sumSubarrayMins(v);
    return 0;
}

Đầu vào

[3,1,2,4]

Đầu ra

17