题解

另一篇题解好像有误，在最差情况下（单调递增或递减），时间复杂度是O(n²)，会超时，数据有点太水了。感觉应该是单调栈搭配差分做

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ff first
#define ss second
#define PII pair
#define VTI vector<int>
#define VTL vector<long long>
using namespace std;
using LL = long long;
const int N = 1e6 + 7;
LL a[N], b[N];
LL d[N], stk[N];
int top = 0, n;

void solve(){
	scanf("%d", &n);
    for (int i = 1;i <= n;i++) scanf("%lld", &a[i]);
    for (int i = 1;i <= n;i++) scanf("%lld", &b[i]);
    VTI l(n + 1), r(n + 2);
    for (int i = 1;i <= n;i++){
    	while(top > 0 && a[stk[top]] <= a[i]) r[stk[top--]] = i - 1;
    	stk[++top] = i;
    }
    while(top > 0) r[stk[top--]] = n;
    for (int i = n;i >= 1;i--){
    	while(top > 0 && a[stk[top]] <= a[i]) l[stk[top--]] = i + 1;
    	stk[++top] = i;
    }
    while(top > 0) l[stk[top--]] = 1;
    
    for (int i = 1;i <= n;i++) //cout << l[i] << ' ' << r[i] << '\n';
    	d[l[i]] += b[i], d[r[i] + 1] -= b[i];
    
    for (int i = 1;i <= n;i++) d[i] += d[i - 1], printf("%lld ", d[i]);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}