题解：UVA1232 SKYLINE

Bobi2014 · 2025-10-05 18:28:19 · 题解

这是一道可癌的线段树题。

前置知识

• 线段树

思路

考虑使用线段树存储区间最小高度、区间最大高度，注意懒标记要赋值为 -1，看完后面的内容你就知道为什么要赋值为 -1 了。build 代码如下：

void build(int p,int l,int r){
    tri[p].l = l,tri[p].r = r,tri[p].tag = -1;
    tri[p].minn = tri[p].maxx = 0;
    if(l == r){ 
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1,l,mid);
    build(p << 1 | 1,mid + 1,r);
}

每次查询时如果区间的最小值已经比这个建筑的高度要高了，那么直接 return，如果这个区间再范围内且最大值小于等于这个建筑的高度，那么把答案加上区间长度，并且将区间全部赋值为这个建筑的高度。pushdown 函数如下：

void pushdown(int p){
    if(tri[p].tag != -1){
        tri[p << 1].tag = tri[p].tag;
        tri[p << 1 | 1].tag = tri[p].tag;
        tri[p << 1].minn = tri[p].tag;
        tri[p << 1 | 1].minn = tri[p].tag;
        tri[p << 1].maxx = tri[p].tag;
        tri[p << 1 | 1].maxx = tri[p].tag;
        tri[p].tag = -1;
    }
}

查询函数的其他部分就和普通的区间查询一样了，注意如果区间在范围内但是最大值比建筑的高度大，那么不能 return 要继续递归。query 函数与 update 的函数的结合体如下：

void update(int p,int l,int r,int val){
    if(tri[p].minn > val){
        return;
    }
    if(tri[p].l >= l and tri[p].r <= r){
        if(tri[p].maxx <= val){
            tri[p].minn = val;
            tri[p].maxx = val;
            tri[p].tag = val;
            ans += (tri[p].r - tri[p].l + 1);
            return;
        }
    }
    pushdown(p);
    int mid = (tri[p].l + tri[p].r) >> 1;
    if(l <= mid){
        update(p << 1,l,r,val);
    }
    if(r > mid){
        update(p << 1 | 1,l,r,val);
    }
    tri[p].minn = min(tri[p << 1].minn,tri[p << 1 | 1].minn);
    tri[p].maxx = max(tri[p << 1].maxx,tri[p << 1 | 1].maxx);
}

最后提醒一下：

多测不清空，爆零两行泪。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int T,Q,ans;
namespace SegmentTree{
    struct node{
        int l,r,minn,maxx,tag;
    } tri[(N << 2) + 5];
    void build(int p,int l,int r){
        tri[p].l = l,tri[p].r = r,tri[p].tag = -1;
        tri[p].minn = tri[p].maxx = 0;
        if(l == r){ 
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1,l,mid);
        build(p << 1 | 1,mid + 1,r);
    }
    void pushdown(int p){
        if(tri[p].tag != -1){
            tri[p << 1].tag = tri[p].tag;
            tri[p << 1 | 1].tag = tri[p].tag;
            tri[p << 1].minn = tri[p].tag;
            tri[p << 1 | 1].minn = tri[p].tag;
            tri[p << 1].maxx = tri[p].tag;
            tri[p << 1 | 1].maxx = tri[p].tag;
            tri[p].tag = -1;
        }
    }
    void update(int p,int l,int r,int val){
        if(tri[p].minn > val){
            return;
        }
        if(tri[p].l >= l and tri[p].r <= r){
            if(tri[p].maxx <= val){
                tri[p].minn = val;
                tri[p].maxx = val;
                tri[p].tag = val;
                ans += (tri[p].r - tri[p].l + 1);
                return;
            }
        }
        pushdown(p);
        int mid = (tri[p].l + tri[p].r) >> 1;
        if(l <= mid){
            update(p << 1,l,r,val);
        }
        if(r > mid){
            update(p << 1 | 1,l,r,val);
        }
        tri[p].minn = min(tri[p << 1].minn,tri[p << 1 | 1].minn);
        tri[p].maxx = max(tri[p << 1].maxx,tri[p << 1 | 1].maxx);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while(T --){
        cin >> Q;
        SegmentTree::build(1,1,N);
        ans = 0;
        while(Q --){
            int l,r,h;
            cin >> l >> r >> h;
            SegmentTree::update(1,l,r - 1,h);
        }
        cout << ans << '\n';
    }
    return 0;
}