P9485

VioletIsMyLove · 2023-10-16 18:24:05 · 题解

首先我们看看如果这道题不能改变海拔，它的答案如何计算。

很显然，对于每个 a_i，它对于答案给出的贡献就是 \min(\max(a_1,a_2,\dots,a_{i-1}),\max(a_{i+1},a_{i+2},\dots,a_n))-a_i。

对于总贡献，只需要调用两个单调栈就能计算。

那如果可以改变海拔呢？

对于任何一个 a_i，我们如果要对它进行操作的话只有两种操作，把它的高度变高或者变低。

首先考虑变高。

如果将 a_i 变高，我们假设它变成 x ，那么 a_i 这个点的贡献就会减少 x-\min(\max(a_1,a_2,\dots,a_{i-1}),\max(a_{i+1},a_{i+2},\dots,a_n)) 。而对于剩余的点，它们的贡献会随着 a_i 的增高而增高。根据最顶上计算贡献的式子，我们会发现当 a_i 低于全图最高点的时候，a_i 的增大不会影响其它点的贡献，只会减少 a_i 本身的贡献。根据 x-\min(\max(a_1,a_2,\dots,a_{i-1}),\max(a_{i+1},a_{i+2},\dots,a_n)) 我们会发现随着 a_i 的增大，a_i 所造成的贡献就会越小，所以为了达成最低的贡献， a_i 的值会变成全图最高点的值。

那如果将 a_i 变低呢？

根据 \min(\max(a_1,a_2,\dots,a_{i-1}),\max(a_{i+1},a_{i+2},\dots,a_n))-a_i 我们会发现如果 a_i 这个点既不是它左边的最高点，也不是它右边的最高点，那么 a_i 的贡献只会变大，这也就是说将 a_i 降低不如不变。

因此如果一个点需要可以降低高度，当且仅当它位于从左到右的单调栈或者从右到左的单调栈内，而它如果会产生贡献，只会发生在出现它是 a_x 任意一侧的最高点的时候，那应该怎么统计呢？

我们会发现，在最开始统计将每个 a_x 变高的时候，就已经做过类似的操作了，我们只需要在将每个 a_i 变高的时候，累计一下会对 a_x 产生影响的值了，而做出的贡献就会在发生改变的那一端除去除了 a_i 以外的最高点。

这题的细节比较多，所以还是放一下代码。

Code:

#include<bits/stdc++.h>
using namespace std;
struct ZS{
    long long h,id;
}st[2][1000005];
long long T,n;
long long top[2],TOP[2];
long long a[1000005],b[1000005],c[1000005];
long long S,s,maxl,maxr;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
int main(){
    T=read();
    while(T--){
        n=read();S=s=maxl=maxr=0;memset(top,0,sizeof top);
        for(int i=1;i<=n;i++)a[i]=read();
        if(n==1){printf("0\n");continue;}
        for(int i=1;i<=n;i++)if(st[0][top[0]].h<=a[i])st[0][++top[0]]=(ZS){a[i],i};
        for(int i=n;i>=1;i--)if(st[1][top[1]].h<=a[i])st[1][++top[1]]=(ZS){a[i],i};TOP[0]=top[0];TOP[1]=top[1];top[0]=0;
        for(int i=1;i<=n;i++){
            if(st[0][top[0]+1].id<=i&&top[0]<TOP[0])maxl=st[0][top[0]++].h;
            else if(i-1!=st[0][top[0]].id)maxl=max(maxl,a[i-1]);
            if(st[1][top[1]].id<i)top[1]--;
            b[i]=max(0ll,min(st[0][top[0]].h,st[1][top[1]].h)-a[i]);
            S+=b[i];s=max(s,b[i]);
            if(i!=st[0][top[0]].id)c[st[0][top[0]].id]+=b[i]-max(0ll,min(maxl,st[1][top[1]].h)-a[i]);
        }
        top[1]=0;top[0]=TOP[0];
        for(int i=n;i>=1;i--){
            if(i<st[0][top[0]].id)top[0]--;
            if(i<=st[1][top[1]+1].id&&top[1]<TOP[1])maxr=st[1][top[1]++].h;
            else if(i+1!=st[1][top[1]].id)maxr=max(maxr,a[i+1]);
            if(i!=st[1][top[1]].id)
            c[st[1][top[1]].id]+=b[i]-max(0ll,min(st[0][top[0]].h,maxr)-a[i]);
        }
        for(int i=1;i<=TOP[0];i++){s=max(s,c[st[0][i].id]);c[st[0][i].id]=0;}
        for(int i=1;i<=TOP[1];i++){s=max(s,c[st[1][i].id]);c[st[1][i].id]=0;}
        printf("%lld\n",S-s);
    }
    return 0;
}