CF1483C Skyline Photo 题解

· · 题解

题目链接
我的Blog

感觉这道题跟当晚的ARC E 撞了，虽然并不是完全一样。
结果我ARC E和这道题都没有在赛时做出来/kk。

这里记 a_i,b_i 为第 i 个楼房的高度和美丽值。 我们设 f_i 为前 i 栋房屋可以得到的最大美丽值，且 \operatorname{val}(l,r) 表示区间 [l,r] 内最矮的楼房的美丽值。 那么显然我们可以得到一个 \mathcal O(n^2) 的转移：

由于 $f_j$ 转移到 $f_i$ 时，只需要用到他们之间的最矮的楼房，所以我们考虑用单调栈来维护所有可能用到的楼房。 维护一个单调递增的栈 $c$（栈中存的是楼房编号），记 $cnt$ 为 $c$ 的大小，满足 $a_{c_i}<a_{c_{i+1}}\space|\space (1 \le i < cnt)$。 那么我们继续考虑转移，同时维护单调栈： 显然，当 $j \in [c_{k-1},c_k-1]\space | \space (1<k \le cnt)$ 时，转移用到的最矮楼房都是 $c_k$。因为根据单调栈的性质，$c_k$ 是 $[c_k,i]$ 中最矮的楼房。 这样，转移方程就变成了 $f_i=\max\limits_{k=2}^{cnt}\{(\max\limits_{j=c_{k-1}}^{c_k-1} f_j) + b_{c_k}\}$。注意在该次转移前已经将单调栈维护到 $i$。 我们可以发现，在从 $f_j$ 转移到 $f_i$ 时，$f_j$ 后面加上的美丽值 $b$ 只跟他后面的第一个栈内元素有关。并且只要该元素不被弹出栈，$f_j$ 后面加上的美丽值永远不变。 那么，我们考虑用线段树维护每一个点的转移值，也就是 $f_j+b$。 在维护单调栈时，对于每一个入栈的元素，我们将区间 $[c_{cnt-1},c_{cnt}-1]$ 全部加上 $b_{c_{cnt}}$。同理，在弹出栈的时候，将该区间全部减去 $b_{c_{cnt}}$。 $f_i$ 的转移就是 $[0,i-1]$ 的区间最小值。 注意在求出 $f_i$ 之后，要单点更新线段树。 最后的 $f_n$ 就是我们要求的答案。 总时间复杂度 $\mathcal O(n \log n)

赛制最后90s码完了这个方法，结果 WA on pretest 6。赛后发现没开 long long /kk。
为了美观和方便理解，只给出未开 long long 的代码。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
const int Maxn=3e5+10;
const int Maxm=Maxn<<2;
const int inf=(1ll<<60);
int a[Maxn],b[Maxn];
int f[Maxn],c[Maxn];
int maxv[Maxm],add[Maxm];
int n,ans;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
inline void push_up(int k)
{
    maxv[k]=max(maxv[k<<1],maxv[k<<1|1]);
}
inline void upd(int k,int v)
{
    add[k]+=v;
    maxv[k]+=v;
}
inline void push_down(int k)
{
    if(add[k]==0)return;
    upd(k<<1,add[k]);
    upd(k<<1|1,add[k]);
    add[k]=0;
}
void modify_seq(int k,int l,int r,int x,int y,int v)
{
    if(x<=l && r<=y)return upd(k,v);
    push_down(k);
    int mid=(l+r)>>1;
    if(x<=mid)modify_seq(k<<1,l,mid,x,y,v);
    if(mid<y)modify_seq(k<<1|1,mid+1,r,x,y,v);
    push_up(k);
}
void modify(int k,int l,int r,int pos,int v)
{
    if(l==r)
    {
        maxv[k]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)modify(k<<1,l,mid,pos,v);
    else modify(k<<1|1,mid+1,r,pos,v);
    push_up(k);
}
int query(int k,int l,int r,int x,int y)
{
    if(x<=l && r<=y)return maxv[k];
    int mid=(l+r)>>1,ret=-inf;
    push_down(k);
    if(x<=mid)ret=query(k<<1,l,mid,x,y);
    if(mid<y)ret=max(ret,query(k<<1|1,mid+1,r,x,y));
    return ret;
}
int main()
{
    // freopen("in.txt","r",stdin);
    n=read();
    for(int i=1;i<=n;++i)
    a[i]=read();
    for(int i=1;i<=n;++i)
    b[i]=read();
    a[0]=-1;
    int cnt=1;
    f[1]=0;
    for(int i=1;i<=n;++i)
    {
        while(a[c[cnt]]>=a[i] && cnt)
        {
            modify_seq(1,0,n,c[cnt-1],c[cnt]-1,-b[c[cnt]]);
            --cnt;
        }
        modify_seq(1,0,n,c[cnt],i-1,b[i]);
        f[i]=query(1,0,n,0,i-1);
        modify(1,0,n,i,f[i]);
        c[++cnt]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}