题解：P10318 [SHUPC 2024] 彭罗斯水槽

Populus_euphratica · 2024-07-23 21:30:04 · 题解

首先来处理环形排列的问题，这个只用把数组复制一遍即可。

接着，考虑如何求解。

先来看一种情况（如下图所示）

黄色部分在箭头所指的位置贡献会消失。

正着考虑有多少贡献太难了，不如反着考虑在哪些时刻会有贡献消失。

考虑如何求出黄色的部分。

可以设一个数组 l 表示左边第一个小于 a_i 的位置，一个数组 r 表示右边第一个小于 a_i 的位置。

所以，就是 l_{i + 1} 到 r_{i - 1} 的贡献会在 r_i 处消失。

那么黄色部分的长度就是 r_i - l_i - 1 但是发现如果有 a_i 相等的情况会算重，所以，考虑把 r 的定义改为在 i 的右边第一个小于等于 a_i 的位置。

那么 l 和 r 数组怎么求？那个单调栈维护一下就行，时间复杂度是 O(n) 的。

那么长度知道了，高度怎么求呢？

发现高度就是 a_i - \max(a_{l_i}, a_{r_i})，为什么呢？可以发现 a_i 是这一段区间里最低的位置，最高处一定是 a_i，而如果前面的没有那么多，就贡献不到后面，后面也同理。可以画个图自己看看。所以要取最大值。

最后答案可以做两边前缀和得到。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn = 200010;
int n;
int Min, sum;
int ans[Maxn];
int a[Maxn], l[Maxn], r[Maxn];
int stk[Maxn], tot;
signed main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    for(int i = n + 1 ; i <= 2 * n ; i++) a[i] = a[i - n];
    for(int i = 1 ; i <= 2 * n ; i++){
        while(a[i] <= a[stk[tot]] && tot) tot--;
        l[i] = stk[tot];
        stk[++tot] = i;
    }
    tot = 0;
    for(int i = 2 * n ; i ; i--){
        while(a[i] < a[stk[tot]] && tot) tot--;
        r[i] = stk[tot];
        stk[++tot] = i;
    }
    a[Min] = 1e18;
    for(int i = 1 ; i <= n ; i++){
        if(a[i] < a[Min]) Min = i;
        sum += a[i];
    }
    for(int i = Min + 1 ; i <= Min + n ; i++){
        if(a[i] == a[Min]) continue;
        int x = r[i] - l[i] - 1;
        int y = a[i] - max(a[l[i]], a[r[i]]);
        // cout << i << " " << a[i] << " " << x << " " << y << '\n';
        ans[1] += y;
        ans[1 + x] -= y;
    }
    for(int i = 1 ; i <= n ; i++) ans[i] += ans[i - 1];
    for(int i = 1 ; i <= n ; i++) ans[i] += ans[i - 1];
    for(int i = 1 ; i <= n ; i++) cout << sum - ans[i] << " ";
    cout << '\n';
    return 0;
}