「题解」「JOISC2020」星座 3 Constellation 3

JOISC2020 D3T1,一道 单调栈 + 笛卡尔树 + 线段树合并 毒瘤题。

题目链接:LibreOJ 3277/JOISC2020 D3T1

题目

题目描述

原题 pdf

翻译

JOI 君拍了一张 $n\times n$ 的星空图,将左起第 $x$ 列,下起第 $y$ 行的像素点称为像素 $(x,y)$。

画面里有白色的大楼,黄色的星星,黑色的空格。第 $i$ 列从最下方到自下数起第 $a _ i$ 行都是白色的大楼。有 $m$ 个星星,第 $j$ 个星星位于像素点 $(x _ j,y _ j)$。此外,所有的像素点都是黑色。

若一个长方形区域可以称作星座,则满足以下条件:

  1. 不含白色像素点。
  2. 至少存在两个星星。

看厌了星座的 JOI 君要把一些黄色的星星涂成黑色,使得没有星座存在。将第 $j$ 个星星涂成黑色会使照片的不自然度增加 $c _ j$,最初不自然度为 $0$。求不自然度的最小值。

数据范围

变量数据范围
$n$$1\leq n\leq 2\times 10^5$
$a _ i$$1\leq a _ i\leq n$
$x _ i,y _ i$$1\leq x _ i,y _ i\leq n$
$c _ i$$\leq 10^9$

时空限制

题目编号时间限制空间限制
JOISC2020 D3T1$1\text{s}$$512\text{MiB}$

题解

思路

显然,对于 删掉一些星星的权值的最小和 等价于 保留一些星星权值的最大值

不难发现,如果我们考虑当前求解区间为 $[l,r]$,则对于区间中最高的建筑 $h _ i$,他会把当前求解区域分割为三个部分:

  1. 比 $h _ i$ 高的一大块。
  2. $h _ i$ 左边。
  3. $h _ i$ 右边。

如图所示,下面是分割的示意图:

JOISC2020-D3T1-Z1.png
JOISC2020-D3T1-Z2.png

图中红色的框框标识了三个部分。

简单讲一下三段的处理方法:

对于 $h _ i$ 左边和 $h _ i$ 的右边我们递归求解即可。

对于比 $h _ i$ 高的一大块。我们不妨使用 线段树 来记录当前求解区间的星星状况,我们以 $y$ 轴坐标作为区间下标,记录星星的权值,则我们只需要求出权值最大的星星即可,即维护区间最大值。

这时如果我们要对答案进行合并,那么我们除了合并线段树外,还要合并左右部分的答案,但我们不难发现,$h _ i$ 左边,$h _ i$ 右边两边互不干扰,所以我们可以直接把这两部分的答案直接加入到当前区间,需要维护一个区间加法的操作。

写出来是这个样子:

inline void merge(reg int x,reg int y,reg int h){
    //将 x 的信息合并到 y 上,h 是 y 对应的高度
    reg ll a=Query(root[x],0,n,0,h),b=Query(root[y],0,n,0,h);
        //查询左右部分的最大值,决定保留
    Update(root[x],0,n,h,n,b),Update(root[y],0,n,h,n,a);
        //左边的最大值加到右边去,右边加到左边去(互相不影响)
    reg ll sum=Query(root[x],0,n,0,h-1)+Query(root[y],0,n,0,h-1);
        //求下方的最大值
    Update(root[x],0,n,h-1,sum);
        //将所有的来自下方的信息保存在 h-1 处
    root[y]=merge(root[x],root[y]);
        //线段树合并
    return;
}
inline void Solve(reg int ID){
    //最高建筑的 id 为 ID
    for(reg int i=0,size=V[ID].size();i<size;++i)
        SegmentTree::Update(root[ID],0,n,V[ID][i].y,V[ID][i].c);
            //插入当前建筑上方的星星
    if(ch[ID][0]){
        //左儿子
        Solve(ch[ID][0]);
            //递归求解
        merge(ch[ID][0],ID,a[ID]);
            //将左儿子的信息合并到当前节点上
    }
    if(ch[ID][1]){
        //右儿子
        Solve(ch[ID][1]);
            //递归求解
        merge(ch[ID][1],ID,a[ID]);
            //将右儿子的信息合并到当前节点上
    }
    return;
}

另外,这样每次找到最大值分割每个序列的操作,显然可以使用笛卡尔树

总的时间复杂度为 $\Theta(n\log _ 2n)$。

还有用树状数组的做法,这里就不详细介绍了。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //无符号快读
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=200000+5;
const int MAXM=200000+5;

int n,m;
int a[MAXN];

namespace SegmentTree{ //动态开点线段树
    const int MAXSIZE=MAXN*80;
    #define mid ( ( (l) + (r) ) >> 1 )
    struct Node{
        int lson,rson; //lson,rson 表示左右儿子
        ll Max,tag; //Max 表示区间最大值,tag 表示加法的懒标记
        #define lson(x) unit[(x)].lson
        #define rson(x) unit[(x)].rson
        #define Max(x) unit[(x)].Max
        #define tag(x) unit[(x)].tag
    };
    int tot;
    int root[MAXN]; //根
    Node unit[MAXSIZE];
    inline int New(void){
        return ++tot;
    }
    inline void pushup(reg int k){ //区间最大值
        Max(k)=max(Max(lson(k)),Max(rson(k)));
        return;
    }
    inline void Add(reg int k,reg ll Val){
        Max(k)+=Val;
        tag(k)+=Val;
        return;
    }
    inline void pushdown(reg int k){ //标记下放
        if(tag(k)){
            if(lson(k))
                Add(lson(k),tag(k));
            if(rson(k))
                Add(rson(k),tag(k));
            tag(k)=0;
        }
        return;
    }
    inline void Update(reg int &k,reg int l,reg int r,reg int pos,ll Val){ //单点修改最大值
        if(!k)
            k=New();
        Max(k)=max(Max(k),Val); //取 max
        if(l==r)
            return;
        pushdown(k);
        if(pos<=mid)
            Update(lson(k),l,mid,pos,Val);
        else
            Update(rson(k),mid+1,r,pos,Val);
        pushup(k);
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int L,reg int R,reg ll Val){ //区间加法
        if(!k)
            return;
        if(L<=l&&r<=R){
            Add(k,Val);
            return;
        }
        pushdown(k);
        if(L<=mid)
            Update(lson(k),l,mid,L,R,Val);
        if(R>mid)
            Update(rson(k),mid+1,r,L,R,Val);
        pushup(k);
        return;
    }
    inline ll Query(reg int k,reg int l,reg int r,reg int L,reg int R){ //区间查询最大值
        if(!k)
            return 0;
        if(L<=l&&r<=R)
            return Max(k);
        pushdown(k);
        if(L<=mid&&mid<R)
            return max(Query(lson(k),l,mid,L,R),Query(rson(k),mid+1,r,L,R));
        else if(L<=mid)
            return Query(lson(k),l,mid,L,R);
        else
            return Query(rson(k),mid+1,r,L,R);
    }
    inline int merge(int x,int y){ //线段树合并
        if(!x||!y)
            return x+y;
        pushdown(x),pushdown(y);
        reg int k=New();
        Max(k)=max(Max(x),Max(y));
        lson(k)=merge(lson(x),lson(y)),rson(k)=merge(rson(x),rson(y));
        return k;
    }
    #undef mid
}

using namespace SegmentTree;

inline void merge(reg int x,reg int y,reg int h){ //将 x 的信息合并到 y 上,h 是 y 对应的高度
    reg ll a=Query(root[x],0,n,0,h),b=Query(root[y],0,n,0,h); //查询左右部分的最大值,决定保留
    Update(root[x],0,n,h,n,b),Update(root[y],0,n,h,n,a); //左边的最大值加到右边去,右边加到左边去(互相不影响)
    reg ll sum=Query(root[x],0,n,0,h-1)+Query(root[y],0,n,0,h-1); //求下方的最大值
    Update(root[x],0,n,h-1,sum); //将所有的来自下方的信息保存在 h-1 处
    root[y]=merge(root[x],root[y]); //线段树合并
    return;
}

struct Star{ //用于储存星星的信息
    int y,c;
    inline Star(reg int y=0,reg int c=0):y(y),c(c){
        return;
    }
};

int ch[MAXN][2];
vector<Star> V[MAXN];

inline void Solve(reg int ID){
    for(reg int i=0,size=V[ID].size();i<size;++i)
        SegmentTree::Update(root[ID],0,n,V[ID][i].y,V[ID][i].c); //插入当前建筑上方的星星
    if(ch[ID][0]){ //左儿子
        Solve(ch[ID][0]); //递归求解
        merge(ch[ID][0],ID,a[ID]); //将左儿子的信息合并到当前节点上
    }
    if(ch[ID][1]){ //右儿子
        Solve(ch[ID][1]); //递归求解
        merge(ch[ID][1],ID,a[ID]); //将右儿子的信息合并到当前节点上
    }
    return;
}

int main(void){
    n=read();
    for(reg int i=1;i<=n;++i)
        a[i]=read(); //读入建筑高度
    static int S[MAXN]; //单调栈
    reg int top=0;
    for(reg int i=1;i<=n;++i){ //单调栈建笛卡尔树
        while(top&&a[i]>=a[S[top]])
            ch[i][0]=S[top--];
        if(top)
            ch[S[top]][1]=i;
        S[++top]=i;
    }
    int Root=S[1]; //标记以下笛卡尔树的根
    m=read();
    reg ll sum=0;
    for(reg int i=1;i<=m;++i){
        static int x,y,c;
        x=read(),y=read(),c=read();
        V[x].push_back(Star(y,c)); //存储星星的信息
        sum+=c; //求综合
    }
    Solve(Root); //开始递归求解
    printf("%lld\n",sum-Query(root[Root],0,n,0,n)); //用总的剪掉保留下的最大的即为答案
    return 0;
}