【算法入门-16】贡献法和单调栈

• 课件

  • 贡献思维和单调栈.pdf

• 单调栈模板

int gao(const vector<int>& a) {
    int n = a.size();

    // L(i): 左边第一个 <= a[i] 的数的下标 
    vector<int> L(n, -1);

    // R(i): 右边第一个 < a[i] 的数的下标
    vector<int> R(n, n);

    vector<int> s(n);  // 用来从左往右放入 a[i]
    int e = 0;  // s 中元素的个数

    for (int i = 0; i < n; i++) {
        // 在 s 里从后往前找到第一个 <= a[i]
        // 拿出的时候确定右边第一个 < a[s[e - 1]] 的就是 a[i]
        while (e > 0 && a[s[e - 1]] > a[i]) R[s[--e]] = i;

        // 放入的时候确定左边第一个 <= a[i] 的
        if (e != 0) L[i] = s[e - 1];
        s[e++] = i;
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + (i64) (i - L[i]) * (R[i] - i) * a[i]) % P;
    }
    return ans;
}