算法竞赛模板

可以求序列中左边/右边第一大/小的元素位置,出栈/入栈可以获得信息

Water Tank

故事

有一个长长的水箱，上面等间隔地放着不同高度的木板。高桥想知道，从水箱的一端倒水时，水到达被木板隔开的每一段的时间。

问题陈述

给你一个长度为 $N$ 的正整数序列： $H=(H _ 1,H _ 2,\dotsc,H _ N)$ .

有一个长度为 $N+1$ 的非负整数序列： $A=(A _ 0,A _ 1,\dotsc,A _ N)$ .最初为 $A _ 0=A _ 1=\dotsb=A _ N=0$ 。

在 $A$ 上重复进行以下运算：

1. 将 $A _ 0$ 的值增加 $1$ 。
2. 依次对 $i=1,2,\ldots,N$ 进行以下操作：
   • 如果 $A _ {i-1}\gt A _ i$ 和 $A _ {i-1}\gt H _ i$ ，则将 $A _ {i-1}$ 的值减少 1，并将 $A _ i$ 的值增加 $1$ 。

求每个 $i=1,2,\ldots,N$ 在 $A _ i\gt 0$ 第一次成立之前的运算次数。

int main() {
    IOS;
    int n;
    cin >> n;
    ll a[n + 1], loc[n + 1];
    ll ans[n + 1];
    memset(ans, 0, sizeof(ans));
    _rep(i, 1, n) cin >> a[i];
    stack<ll> s; //递减
    _rep(i, 1, n) { // 单调栈寻找每个元素左边第一个大于等于它的元素位置
        while (!s.empty() && a[s.top()] < a[i]) {
            s.pop();
        }
        loc[i] = s.empty() ? 0 : s.top();
        s.push(i);
    }
    _rep(i, 1, n) {
        if(loc[i] == 0) {
            ans[i] = i*a[i] + 1;
        } else {
            ans[i] = ans[loc[i]] + (i - loc[i])*a[i];
        }
    }
    _rep(i, 1, n) {
        cout << ans[i] << " ";
    }
    return 0;
}