题解：CF2234F Vessels, Heights and Two Versions (Hard Version)

MaxBlazeResFire · 2026-06-10 09:45:23 · 题解

倍长序列。根据简单版本我们可以得到结论：i 的答案就是将 (i,i+n) 这一段拿出来后，最大值左侧每个位置填前缀最大值，右侧每个位置填后缀最大值后，所有数的和。

容易单调栈维护。以前缀最大值为例，维护出每个数 i 右侧首个大于它的数 r_i，那么 [i,r_i) 中间全都填 h_i，贡献 h_i(r_i-i)。

取一个最大值标志物预处理前后缀答案，可以直接拼起来做到 O(n)。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 400005

int n,h[MAXN],st[MAXN],f[MAXN],g[MAXN],top;

inline void solve(){
    scanf("%lld",&n);
    int mxid = 0;
    for( int i = 1 ; i <= n ; i ++ ){
        scanf("%lld",&h[i]);
        if( h[i] > h[mxid] ) mxid = i;
        h[i + n] = h[i];
    }
    for( int i = mxid + n ; i >= 1 ; i -- ){
        while( top && h[i] > h[st[top]] ) top --;
        f[i] = f[st[top]] + h[i] * ( st[top] - i );
        st[++top] = i;
    }
    top = 0;
    for( int i = mxid ; i <= 2 * n ; i ++ ){
        while( top && h[i] > h[st[top]] ) top --;
        g[i] = g[st[top]] + h[i] * ( i - st[top] );
        st[++top] = i;
    }
    for( int i = 1 ; i <= n ; i ++ ){
        int ans = f[i];
        int lst = i == 1 ? n : n + i - 1;
        ans += g[lst];
        printf("%lld ",ans);
    }
    for( int i = 1 ; i <= 2 * n ; i ++ ) h[i] = f[i] = g[i] = st[i] = 0;
    top = 0;
    puts("");
}

signed main(){
    int t; scanf("%lld",&t);
    while( t -- ) solve();
    return 0;
}