AGC005B Minimum Sum

LuoGu: AT2060 [AGC005B] Minimum Sum

AtCoder: B - Minimum Sum

将贡献拆开了看，即为每个数乘上以这个数为最小值的区间的数量（即这个数前面的连续的比它小的个数乘上后面的），所以我们计算 $l _ i$ 和 $r _ i$ ，表示 $l _ i$ 到 $ i - 1$ 都比它小， $i +1$ 到 $r _ i - 1$ 都比它大。为了防止边界问题，将所有的 $l _ i$ 都先赋为 $1$ ，$r _ i$ 为 $n$ 。对于每一个数，在单调栈里一直取元素，如果比它大了，那么 $r _ {stk.top()} = i - 1$ ，同时 $l _ i = stk.top + 1$ 。当 $top = 0$ 时，即当前时最小的，$l _ i = 1$ ，将 $stk[0] = 0$ ，可以方便不用特判栈为空。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int top, stk[N];
int n, w[N], l[N], r[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++)
        l[i] = 1, r[i] = n;
    for (int i = 1; i <= n; i++)
    {
        while (top && w[stk[top]] > w[i])
            r[stk[top--]] = i - 1;
        l[i] = stk[top] + 1;
        stk[++top] = i;
    }
    LL res = 0;
    for (int i = 1; i <= n; i++)
        res += (LL)w[i] * (i - l[i] + 1) * (r[i] - i + 1);
    printf("%lld", res);
    return 0;
}