题解

看到大佬用单调栈做，但我没学过，所以用了ST表+二分+差分做.
扩散分为左，右两个部分
我们注意到 $[l,i-1]$ 与 $[i+1,r]$ 区间的高度最大值满足单调性，可以预处理最大值 $O(1)$ 查询，二分即可.

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[1000005], b[1000005];
long long add[1000005];
int st[21][1000005];
inline int get(int l, int r){//查询
	int len = r - l + 1;
	int i = log2(len);
	return max(st[i][l], st[i][r - (1 << i) + 1]);
}
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], st[0][i] = a[i];
	for(int i = 1; (1 << i) <= n; i++){
		for(int j = 1; j + (1 << i) - 1 <= n; j++){
			st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i >> 1)]);//预处理ST表
		}
	}
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++){
		int reall, realr;
		int l = 1, r = i - 1;
		while(l <= r){
			int mid = l + r >> 1;
			if(get(mid, i - 1) >= a[i]) l = mid + 1;//二分求最远
			else r = mid - 1;
		}
		reall = l;
		l = i + 1, r = n;
		while(l <= r){
			int mid = l + r >> 1;
			if(get(i + 1, mid) >= a[i]) r = mid - 1;
			else l = mid + 1;
		}
		realr = r;
		add[reall] += b[i], add[realr + 1] -= b[i];//区间加
	}
	for(int i = 1; i <= n; i++) cout << (add[i] += add[i - 1]) << ' ';//计算前缀和

	return 0;
}