【官方题解】单调栈

【题目大意】

在一条线段上有 $n$ 座有高度的能量塔每个能量塔都能散发一个能量扩散至碰到第一个高度大于等于这座能量塔的位置截至，期间所以有位置获得 $a_i$ 的能量不包括阻挡能量扩散的那座塔的位置。

题目要求求这 $n$ 个位置的能量。

Subtask：100%

【算法分析】

本题采用单调栈算法

两次循环分别从前后两个方向进行单调栈，单调栈高度，并记录此时还在单调栈中能量塔的总能量。

对于循环至第 $i$ 座能量塔时，我们可以用一个数组 $c$ 来记录单调栈里剩余的能量，这也是全能达到 $i$ 的能量，之后再将第 $i$ 座能量塔入栈。

最终结果就是前后单调栈记录的结果以及自身散发的的能量。

时间复杂度 O(n) 。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[1000006],b[1000006];
ll c[1000006];
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	for (int i=1;i<=n;i++){
		cin>>b[i];
	}
	stack<ll> stk;
	ll z=0;
	for (int i=1;i<=n;i++){
		while(!stk.empty()&&a[stk.top()]<=a[i]) z-=b[stk.top()],stk.pop();
		c[i]+=z;
		z+=b[i];
		stk.push(i);
	}
	while(!stk.empty()) stk.pop();
	z=0;
	for (int i=n;i>=1;i--){
		while(!stk.empty()&&a[stk.top()]<=a[i]) z-=b[stk.top()],stk.pop();
		c[i]+=z;
		z+=b[i];
		stk.push(i);
	}
	for (int i=1;i<=n;i++){
		cout<<b[i]+c[i]<<' ';
	}
    return 0;
}