AT_abc480_g 题解

· · 题解

这个 G 很简单啊，居然只过了不到三百人（指指点点。

哦我怎么赛后 5min 才过，我是区区！我爱蠕动！我要飞起来！

做完 F 后给我的时间不多了。

严肃阅读了 G 题并意识到与某道最近的模拟赛 T2 维护 \min 和 \max 的思想非常类似，于是就加快写了一下。

首先你可以发现有基础的 O(n^2) dp，令 dp_i 表示以 i 为结尾的最小权值，那么显然有转移 dp_i = \min_{j < i} dp_{j-1} + \max(a_j,a_{j+1},\dots,a_i) - \min(a_j,a_{j+1},\dots,a_i) 这样。

前面的 \min 其实不难维护，关键在于后面的 + \max - \min 这个结构的东西。

不难想到单调栈维护当前的 \max 和 \min 区间（针对 \max 和 \min 开两个单调栈）情况，每次加入一个新的 a_i 后就用自身数值尝试更新单调栈情况，当单调栈栈顶弹出区间后，我们就将这段区间原本的 \max 或 \min 贡献删去并累加新的。而每次 dp 转移的时候只需要查询一个前缀 \min 值就可以了。也就是说我们只需要维护一棵支持区间加和区间 \min 的线段树，这是简单的。

那么就做完了，实现上有一些细节，需要调一阵子（要不是因为我调了好一会我赛时都做出来了 www），具体可以参考一下我的代码喵。

我的代码里也有很多调试记录（为了观感，下面展出的代码将调试删掉了），在 submission 里其实也可以看到我是调的挺烦的。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL INF = 2e18+1099;
struct node{LL l,r,val;};
struct SegT{LL val,tag;}t[N<<2];
LL n,a[N],dp[N];
int mx_top,mn_top;
node mx_st[N],mn_st[N];
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int ls(int u){return (u<<1);}
int rs(int u){return (u<<1|1);}
void push_up(int u){
    t[u].val=min(t[ls(u)].val,t[rs(u)].val);
    return;
}
void add_tag(int u,LL k){
    t[u].val+=k,t[u].tag+=k;
    return;
}
void push_down(int u){
    if(!t[u].tag)return;
    add_tag(ls(u),t[u].tag);
    add_tag(rs(u),t[u].tag);
    t[u].tag=0;return;
}
void change(int u,int l,int r,int L,int R,LL k){
    if(r<L||R<l)return;
    if(L<=l&&r<=R){add_tag(u,k);return;}
    int mid=(l+r)>>1;push_down(u);
    change(ls(u),l,mid,L,R,k);
    change(rs(u),mid+1,r,L,R,k);
    push_up(u);return;
}
LL ask(int u,int l,int r,int L,int R){
    if(R<L||r<L||R<l)return INF;
    if(L<=l&&r<=R)return t[u].val;
    int mid=(l+r)>>1;push_down(u);
    return min(ask(ls(u),l,mid,L,R),ask(rs(u),mid+1,r,L,R));
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    change(1,1,n+1,1,1,0);
    for(int i=1;i<=n;i++){
        int now=i;
        while(mx_top&&mx_st[mx_top].val<=a[i]){
            node tmp=mx_st[mx_top--];
            change(1,1,n+1,tmp.l,tmp.r,a[i]-tmp.val);
            now=tmp.l;
        }
        mx_st[++mx_top]={now,i,a[i]};
        now=i;
        while(mn_top&&mn_st[mn_top].val>=a[i]){
            node tmp=mn_st[mn_top--];
            change(1,1,n+1,tmp.l,tmp.r,tmp.val-a[i]);
            now=tmp.l;
        }
        mn_st[++mn_top]={now,i,a[i]};
        dp[i]=ask(1,1,n+1,1,i-1);
        change(1,1,n+1,i+1,i+1,dp[i]);
    }
    cout<<dp[n]<<"\n";
    return 0;
}

::::

或许，这也算是某种意义上的第一次切 G 了呢？至少曾经的任何一道 G 都没有在不看题解的情况下补出来过。

不过我还是相信我能够飞起来的。

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！