ผลรวมของค่าต่ำสุดของซับอาร์เรย์ทั้งหมดใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม A ต้องหาผลรวมของ min(B) สำหรับทุกซับอาร์เรย์ B ที่ต่อเนื่องของ A เนื่องจากคำตอบอาจใหญ่มาก ให้คืนค่า modulo 10^9 + 7

ตัวอย่าง: [3,1,2,4] ผลลัพธ์: 17
ซับอาร์เรย์: [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]
ค่าต่ำสุด: [3,1,2,4,1,1,2,1,1,1] ผลรวม = 17

ขั้นตอนการแก้ปัญหา (Monotonic Stack + Contribution)

• MOD := 1e9 + 7
• ฟังก์ชัน add(a,b) และ mul(a,b) สำหรับ modulo arithmetic
• ใช้ Stack หา left[i] = ดัชนีซ้ายสุดที่ A[left] < A[i] และ right[i] = ดัชนีขวาสุดที่ A[right] <= A[i]
• สำหรับแต่ละ i คำนวณจำนวนซับอาร์เรย์ที่ A[i] เป็นค่าต่ำสุด:
  • leftBound := i - left[i] - 1
  • rightBound := right[i] - i - 1
  • contri := 1 + leftBound + rightBound + leftBound * rightBound
  • ans := add(ans, mul(contri, A[i]))

ตัวอย่างโค้ด (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);
        vector <int> right(n, n);
        int ans = 0;
        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);
        }
        for(int i = 0; i < n; i++) {
            int leftBound = i - (left[i] + 1);
            int rightBound = (right[i] - 1) - i;
            int contri = 1 + leftBound + rightBound + (leftBound * rightBound);
            ans = add(ans, mul(contri, A[i]));
        }
        return ans;
    }
};

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

อินพุต

[3,1,2,4]

เอาต์พุต

17