CF1483C Skyline Photo 题解
Priori_Incantatem
2021-03-22 10:58:53
[题目链接](https://www.luogu.com.cn/problem/CF1483C)
[我的Blog](https://blog.csdn.net/Brian_Pan_/article/details/115065320?spm=1001.2014.3001.5501)
感觉这道题跟当晚的ARC E 撞了，虽然并不是完全一样。
结果我ARC E和这道题都没有在赛时做出来/kk。
这里记 $a_i,b_i$ 为第 $i$ 个楼房的高度和美丽值。
我们设 $f_i$ 为前 $i$ 栋房屋可以得到的最大美丽值，且 $\operatorname{val}(l,r)$ 表示区间 $[l,r]$ 内最矮的楼房的美丽值。
那么显然我们可以得到一个 $\mathcal O(n^2)$ 的转移：
$f_i=\max\limits_{j=0}^{i-1}\{f_j+\operatorname{val}(j+1,i)\}$。
由于 $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` 的代码。
```cpp
#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;
}
```