BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 23 题

第 2 题

（区间统计问题）给定两个长为 $n$ 的数列 $a, b$，求如下式子的值：

$$\sum_{l=1}^n \sum_{r=l}^n \max(a_l,a_{l+1},\dots,a_r)\times b_r$$

该代码枚举区间右端点，使用单调栈维护所有后缀最大值，不断更新答案，时间复杂度 $O(n)$。代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000011;

int n, a[N], b[N];
int stk[N], top;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
    long long sum = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        while (top && ___①___) {
            sum -= ___②___;
            --top;
        }
        sum += ___③___;
        ans += ___④___;
        ___⑤___;
    }
    cout << ans << endl;
    return 0;
}

1. ①处应该填（ ） A. a[stk[top]] >= a[i] B. a[stk[top]] <= a[i] C. b[stk[top]] >= b[i] D. b[stk[top]] <= b[i] 2. ②处应该填（ ） A. stk[top] - stk[top - 1] + 1 B. `1ll * (stk[top] - stk[top

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考单调栈维护区间最大值。拿到题先想：枚举右端点 i 时，哪些左端点 l 能取到 max(a[l..i])=a[i]？答案就是 stk[top] 到 i 这段。栈里存的是下标，遇到更小的 a[i] 就把栈顶弹出，直到栈顶值大于 a[i]，弹出区间贡献要减去，最后把 i 压栈，sum 里加上 a[i] 乘以这段长度。

容易把栈里当存值，其实存的是下标；弹出时区间长度是 stk[top] - stk[top-1]，别多写 +1 或漏写，sum 要减去这段 a[stk[top]] 的贡献，别只减 a[i]；压栈时是 stk[++top]=i，千万别写成存 a[i] 或 top++ 顺序反了，否则栈里全是值或下标混乱，后面算长度全错。

这道题是 BCSP-X 2024 第 23 题，核心考查单调栈在区间最大值统计中的应用。题目要求计算所有右端点为 i 时，max(a[l..i])×b[i] 的和，再对 i 求和。直接枚举 l 是 O(n²)，必须用单调栈优化到 O(n)。命题人喜欢在这里挖坑：栈里存的是下标，不是值；更新 sum 时要减去弹出区间的贡献，而不是只减当前 a[i]；压栈时是 i 不是 a[i]。这些细节一旦搞错，后面所有计算全崩。拿到题先想：当右端点走到 i 时，哪些左端点 l 能让 max(a[l..i]) 恰好等于 a[i]？显然是从上一个比 a[i] 大的元素下标 +1 到 i 这一段。我们用单调栈维护一个下标序列，保证对应 a 值严格递减。每遇到新的 a[i]，就把栈顶所有比 a[i] 小的下标弹出，弹出的每一段区间，之前 sum 里都加了 a[stk[top]] 的贡献，现在最大值变了，得把那段贡献减掉。弹出的区间长度是 stk[top] - stk[top-1]（注意没有 +1），所以 sum -= (stk[top] - stk[top-1]) * a[stk[top]]。弹出结束后，sum 里剩下的就是当前 a[i] 对这段区间的贡献，即 sum += (i - stk[top]) * a[i]。然后 ans += sum * b[i]。最后把 i 压栈，stk[++top] = i。这样每轮循环 O(1) 摊还，总 O(n)。现在逐空填：①处是弹出条件，栈顶值要小于等于当前值才弹，所以填 a[stk[top]] <= a[i]（选 B）。②处是减去弹出区间的贡献，长度是 stk[top] - stk[top-1]，乘以 a[stk[top]]，别忘了 long long，选 D。③处是加上当前 a[i] 的贡献，长度是 i - stk[top]，选 D。④处是 ans 加 sum*b[i]，选 B。⑤处是压栈，存下标 i，且先++top 再赋值，选 C。这些坑点正是命题人最爱设的，比如把②写成 +1 或者只减 a[i]，把⑤写成存 a[i]，都会导致答案错得离谱。考频上看，单调栈在 CSP-J/S 里出现频率中等，近三届约 8-10 次，常与区间最大值、最小值、矩形面积等结合，今年这道题就是典型。未来可能继续考单调栈变种，比如多值维护、带权区间和，或者和线段树、树状数组结合做动态版本，但基础单调栈的考法不会变，因为它是处理区间极值的利器。总之，这题只要理清栈存下标、弹出区间长度、sum 加减逻辑，就能稳稳拿分，别被那些看起来像值的选项带偏了。