https://www.luogu.com.cn/problem/P2422

1. 题目理解

给出连续 N 天的感受值 A1, A2, …, AN。

舒适度 = 区间中 最小感受值 × 区间中 所有感受值的和。

要求：找出一个区间 [l, r]，让舒适度最大。

例子

N = 6
A = [3, 1, 6, 4, 5, 2]

如果我们选第 3 天到第 5 天：

区间 = [6, 4, 5]

• 区间和 = 6 + 4 + 5 = 15
• 区间最小值 = 4
• 舒适度 = 15 × 4 = 60

2. 暴力做法（会超时）

想法：

1. 枚举所有区间 [l, r]
2. 求区间最小值
3. 求区间和
4. 计算舒适度 = 最小值 × 区间和

时间复杂度：

总复杂度 O(n³) ❌ 不可行

枚举区间 O(n²)

每次再扫一遍 O(n)

3. 正确高效解法

核心思想

把每一天的感受值 A_i 当作区间的最小值，看看它能往左、往右扩多大。

例如：

如果 A_i 是 4，那么它是区间最小值，

那么我们想知道：

• 左边可以扩到的最远位置 L[i]（左边第一个比它小的数 + 1）
• 右边可以扩到的最远位置 R[i]（右边第一个比它小的数 – 1）

这样，i 作为最小值时的最大区间就是 [L[i], R[i]]。

然后计算：

舒适度 = A[i] * (S[R[i]] – S[L[i]-1])

其中 S 是前缀和。

4. 单调栈求左右边界

我们用一个 单调递增栈 来求左右边界。

左边界 L[i]

：

• 从左到右扫描
• 栈里存下标
• 如果栈顶比当前大或等于 → 弹出（因为当前更小，覆盖它）
• 弹完后：
  • 如果栈空 → L[i] = 1
  • 否则 L[i] = 栈顶下标 + 1
• 把 i 压栈

---

右边界 R[i]

：

• 从右到左扫描
• 同理：
  • 如果栈顶比当前大 → 弹出
  • 弹完后：
    • 如果栈空 → R[i] = n
    • 否则 R[i] = 栈顶下标 – 1
• 把 i 压栈

5. 手算示例

A = [3, 1, 6, 4, 5, 2]

求 L[i]

i	A[i]	L[i]	解释
1	3	1	左边没比它小的
2	1	1	左边没比它小的
3	6	3	左边第一个比 6 小的是自己
4	4	3	左边第一个比 4 小的是 6 左边的 1
5	5	3	左边第一个比 5 小的是 4
6	2	2	左边第一个比 2 小的是 1

求 R[i]

i	A[i]	R[i]	解释
6	2	6	右边没比它小的
5	5	5	右边第一个比 5 小的是 2
4	4	5	右边第一个比 4 小的是 2
3	6	5	右边第一个比 6 小的是 4
2	1	6	右边没比它小的
1	3	1	右边第一个比 3 小的是 1

6. 最后计算舒适度

用前缀和 S：

S = [0, 3, 4, 10, 14, 19, 21]

枚举每个 i：

舒适度 = A[i] * (S[R[i]] – S[L[i]-1])

i	A[i]	L[i]	R[i]	区间和	舒适度
1	3	1	1	3	9
2	1	1	6	21	21
3	6	3	5	15	90 ❌（最小值不是 6）
4	4	3	5	15	60 ✅
5	5	3	5	15	75 ❌
6	2	2	6	20	40

最大舒适度 = 60。

7. 完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
typedef long long LL;
typedef list<int>::iterator Iter;
vector<LL> a(N + 2, 0), sum(N + 2, 0);
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    vector<int> l(n + 2), r(n + 2);
    deque<int> dq;
    for (int i = 1; i <= n; i ++ ) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        if (dq.empty()) l[i] = 1;
        else l[i] = dq.back() + 1;
        dq.push_back(i);
    }
    dq.clear();
    for (int i = n; i >= 1; i -- ) {
        while (!dq.empty() && a[dq.back()] > a[i]) dq.pop_back();
        if (dq.empty()) r[i] = n;
        else r[i] = dq.back() - 1;
        dq.push_back(i);
    }
    LL ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        LL summ = sum[r[i]] - sum[l[i] - 1];
        ans = max(ans, summ * a[i]);
    }
    cout << ans;
    return 0;
}

8. 总结

• 核心思想：把每个位置当作最小值
• 关键点：
  • 单调栈找左右边界
  • 前缀和快速求区间和
  • O(n) 解决