【UVA1232】SKYLINE

线段树简单题。

简化题意

依次给出 \(n\) 个区间 \([l_i,r_i]\)，这个区间的值 \(h_i\)，求出这个区间内小于 \(h_i\) 的位置个数累计求和，然后把这些位置覆盖为 \(h_i\)。

解题思路

容易想到线段树，维护区间最小值和区间覆盖值。

当 query 到某个区间时，若最小值都比 \(h_i\) 大，显然不会有小于 \(h_i\) 的值；如果覆盖值比 \(h_i\) 小，那么结果加上区间长度 \(len=r-l+1\)。

然后就没有了。

仅给出线段树的实现。

#define lc(id) id<<1
#define rc(id) id<<1|1
inline void push_up(int id)
{
    tree[id]=min(tree[lc(id)],tree[rc(id)]);
    return ;
}//tree[] 维护区间最小值
inline void build(int l,int r,int id)
{
    if(l==r)
    {
        tag[id]=inf;
        tree[id]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,lc(id));
    build(mid+1,r,rc(id));
    push_up(id);//别忘了上传
    return ;
}
inline void push_down(int id)
{
    if(tag[id]!=inf)//有tag
    {
        tag[lc(id)]=tag[id];
        tree[lc(id)]=tag[id];
        tag[rc(id)]=tag[id];
        tree[rc(id)]=tag[id];
        tag[id]=inf;
    }
    return ;
}
inline void update(int ql,int qr,int h,int l,int r,int id)//update 的同时求值
{
    if(tree[id]>h)//最小值都比h大了，没必要做下去
    	return;
    if(ql<=l&&r<=qr)//完全在目标区间中
    {
        if(tag[id]<=h&&tag[id]!=inf)
        {
            ret+=r-l+1;
            tag[id]=tree[id]=h;
            return;//return 放里面！！！如果不满足 if 的条件还要再往下
        }
    }
    push_down(id);//先下传
    int mid=(l+r)>>1;
    if(ql<=mid)
        update(a,b,h,l,mid,lc(id));
    if(qr>mid)
        update(a,b,h,mid+1,r,rc(id));
    push_up(id);
}