良好的感觉

单调栈 最小值覆盖到的区间 T3

P2422 良好的感觉 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 $A_i$，$A_i$ 越大，表示人感觉越舒适。在一段时间 $\left[i,j\right]$ 内，人的舒适程度定义为 $\left[i,j\right]$ 中最不舒服的那一天的感受值 $\times$ $\left[i,j\right]$中每一天感受值的和。现在给出 kkk 在连续 $N$ 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

输入格式

第一行为 $N$，代表数据记录的天数。

第二行 $N$ 个整数，代表每一天的感受值。

输出格式

一行，表示在最舒适的一段时间中的感受值。

样例 #1

样例输入 #1

6
3 1 6 4 5 2

样例输出 #1

60

提示

kkk 最开心的一段时间是第 $3$ 天到第 $5$ 天，开心值：$(6+4+5)\times 4=60$。

对于 $30\%$ 的数据，$1\le N\le 100$。

对于 $70\%$ 的数据，$1\le N\le 2000$。

对于 $100\%$ 的数据，$1\le N\le 100000$，$1\le \text{感受值}\le 1000000$。

思路

数据范围规定没有负数，所以前缀和绝对是会越来越大的，应该优先考虑那个最不舒服的值。

可以发现这样一个性质：

对于任意一个点 $a_i$, 找其左边第一个 $a_l<a_i$ 的 $a_l$, 右边第一个 $a_r<a_i$ 的 $a_r$。此时, 在 $[l+1,r-1]$ 区间内, 最优解就是 $a_i$, 也就是说, 最终答案只会在这样的区间中存在。

我们只需要发现一种方法能快速枚举这样的区间就行。

那么有没有一种方法能在 $O(n)$ 的复杂度得到所有满足条件的区间呢？ 使用单调栈就行, 当新元素 $a_j<a_{tail}$ 时, 弹出 $a_{tail}$ 并入栈 $a_j$。再定义 $f_i$ 为 $a_i$ 所对应的最大区间和。

此时可以发现, 当出现满足 $a_j<a_{tail}$ 的 $a_j$ 时, $a_{tail}$ 右边的第一个小于值就是 $a_r=a_j$, 此时加上 $a_{tail}$ 的右区间和 $s[j-1]-s[tail]$。

而它的左区间就是在还未加入队列前, 设此时为 $a_i$, 此时因为在加入队列前会先更新栈尾, 把 $a_{tai{l}^{\prime }}>a_i$ 的都给弹飞, 那么留下来的就是最小值, 满足 $a_i>a_{tai{l}^{\prime }}$。

更新完栈尾后, 当前的 $a_i$ 所对应的左区间和就是 $s[i]-s[tai{l}^{\prime }]$。

因此, 对于每一个可能的最小值 $a_i$ , 其能达到的区间和就是 $f_i=(s[i]-s[tai{l}^{\prime }])+(s[j-1]-s[i])$, 只会加这两次。

单调队列/栈的题目真烦啊啊啊啊啊啊啊啊

代码

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
LL a[N], s[N], q[N], f[N];
 
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    n++, a[n] = 0, s[n] = s[n - 1];
 
    int tail = 0;
    for (int i = 1; i <= n; i++)
    {
        while (a[q[tail]] > a[i])
        {
            f[q[tail]] += s[i - 1] - s[q[tail]];
            tail--;
        }
        f[i] = s[i] - s[q[tail]];
        q[++tail] = i;
    }
 
    LL res = 0;
    for (int i = 1; i < n; i++)
        res = max(res, f[i] * a[i]);
    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}