题解星座 3

Saliеri · 2021-06-27 11:25:00 · 题解

妙妙题。

首先先考虑一些最基本的性质：

我们考虑白色的部分对构成星座所产生的的影响。

可以发现，两颗星星能否构成星座只与他们之间的白色区域高度的 区间最大值 有关。

看到区间最大值就可以直接上笛卡尔树了。

我们对白色区域的高度建出大根笛卡尔树后，考虑关于计算答案的一堆事情：

在每一个点上保存什么信息？
如何合并笛卡尔树上左右子树的信息？

对于第一个问题：最少需要删去多少价值的星星不是很友好，所以我们换成最多能保存多大价值的星星。

只保存这个信息自然是不够的，考虑需要加个什么维度来消后效性。

接着会有一个比较明显的限制——在当前子树的最大值之上最多只能有一颗星星。

意思就是说，左右子树中最高的星星的高度会影响当前的决策。

那么每一个位置的状态就可以设为：f_{u,h} 表示 u 的子树内最高的星星高度为 h，最多能保留的星星的价值。

接下来考虑第二个问题：如何合并。现在设当前节点为 p，这个节点的白色区域高度为 v，正在合并的两个点为 x,y。

对于 v 以上的部分，因为最多只能有一个点存在，并且中间有白色区域来隔断，所以一边比 v 高的部分都可以接受另一边小于等于 v 的部分的贡献。

形式化地：\begin{cases}valx = \max_{1\leq h \leq v}f_{x,h}\\valy = \max_{1\leq h \leq v}f_{y,h}\\ f_{p,h} \leftarrow \max(f_{x,h}+valy,f_{y,h}+valx) \quad v<h\leq n\end{cases}

对于高度小于等于 v 的位置，直接处理每个位置不是很方便。

但是观察上面的转移柿子：我们所关心的只是前缀最大值而已。

所以更低的位置的具体值不再需要被用到。所以只需要拿可能的最大值更新 v 这一个位置即可。

换句话说：f_{p,v} \leftarrow valx+valy。

接下来考虑怎么去维护这么一个 DP。

区间加、区间 max、合并——线段树合并维护即可。

因为就是一个裸的线段树合并，所以总复杂度就是非常漂亮的 O(n\log n)。

可以感觉到这个做法还是非常无脑的，所以时空常数会比较大。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using std::max; 
typedef long long ll;
const int maxn = 2e5+5;
int n,m,a[maxn],tr[maxn][2],st[maxn],top;
struct pair{int x,y;pair(int X=0,int Y=0):x(X),y(Y){};};
std :: vector <pair> star[maxn];
int rt[maxn],ch[maxn<<6][2],tot;
ll maxx[maxn<<6],tag[maxn<<6],sumall;
void gtag(int x,ll v){if(x)tag[x] += v,maxx[x] += v;}
void psd(int x){if(tag[x])gtag(ch[x][0],tag[x]),gtag(ch[x][1],tag[x]),tag[x]=0;}
void ins(int &u,int l,int r,int p,ll v){
    if(!u)u = ++tot;maxx[u] = max(maxx[u],v);
    if(l == r)return ;
    int mid = l+r>>1;psd(u);
    p<=mid?ins(ch[u][0],l,mid,p,v):ins(ch[u][1],mid+1,r,p,v);
}
void mdf(int u,int l,int r,int x,int y,ll v){
    if(!u||l>y||r<x)return ;
    if(l>=x&&r<=y)return gtag(u,v);
    int mid = l+r>>1;psd(u);
    mdf(ch[u][0],l,mid,x,y,v),mdf(ch[u][1],mid+1,r,x,y,v),maxx[u]=max(maxx[ch[u][0]],maxx[ch[u][1]]);
}
ll query(int u,int l,int r,int x,int y){
    if(!u||l>y||r<x)return 0;
    if(l>=x&&r<=y)return maxx[u];
    int mid = l+r>>1;psd(u);
    return max(query(ch[u][0],l,mid,x,y),query(ch[u][1],mid+1,r,x,y));
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    int now = ++tot;
    psd(x),psd(y);
    maxx[x] = max(maxx[x],maxx[y]);
    ch[x][0] = merge(ch[x][0],ch[y][0]),ch[x][1] = merge(ch[x][1],ch[y][1]);
    return x;
}
void Merge(int x,int y,int v){
    ll lef = query(rt[x],1,n,1,v),rig = query(rt[y],1,n,1,v);
    mdf(rt[x],1,n,v+1,n,rig),mdf(rt[y],1,n,v+1,n,lef);
    lef = query(rt[x],1,n,1,v),rig = query(rt[y],1,n,1,v);
    rt[x] = merge(rt[x],rt[y]),ins(rt[x],1,n,v,lef+rig);
}
void DFS(int u){
    for(int i=0;i<star[u].size();++i)
        ins(rt[u],1,n,star[u][i].x,star[u][i].y);
    if(tr[u][0])DFS(tr[u][0]),Merge(u,tr[u][0],a[u]);
    if(tr[u][1])DFS(tr[u][1]),Merge(u,tr[u][1],a[u]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        int k = top;
        while(top && a[st[top]]<a[i])--top;
        tr[i][0] = (k==top?0:st[top+1]),tr[st[top]][1] = i,st[++top] = i;
    }
    scanf("%d",&m);
    for(int i=1,x,y,c;i<=m;++i)scanf("%d %d %d",&x,&y,&c),star[x].push_back(pair(y,c)),sumall+=c;
    DFS(tr[0][1]),printf("%lld\n",sumall-maxx[rt[tr[0][1]]]);
    return 0;
}

题解 星座 3

题解星座 3