题解：UVA1232 SKYLINE

· · 题解

前言：

主播写完作业后百无聊赖切的一道水题。

思路：

看见区间上维护最大值就可以考虑线段树了。维护一个最大值和一个最小值，表示在当前区间内最高的建筑和最矮的建筑。若建筑物的高度大于所在区间的最大值，则直接更新。用 ans 累加区间长度。若建筑物的高度小于所在区间的最小值，显然对之后的数据没有影响，不需要继续递归下去。

另外，由于区间修改，记得懒标记。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define gc getchar
#define pb push_back
#define ls u<<1
#define rs u<<1|1
template<typename T>inline void read(T&x){x=0;int f=1;char ch=gc();while(!isdigit(ch)){if(ch=='-') f=-1;ch=gc();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}x*=f;}
template<typename T,typename ...T1>inline void read(T&x,T1&...x1){read(x);read(x1...);}
const int ri=1e5+5,ru=1e5; LL ans;
struct _{LL minn,maxn,lazy;}tr[ri<<2];
void pushdown(int u){
    if(tr[u].lazy!=-1){
      tr[ls].maxn=tr[ls].minn=tr[u].lazy;
      tr[rs].maxn=tr[rs].minn=tr[u].lazy;
      tr[ls].lazy=tr[rs].lazy=tr[u].lazy;
      tr[u].lazy=-1;
    }
}
void pushup(int u){
    tr[u].minn=min(tr[ls].minn,tr[rs].minn);
    tr[u].maxn=max(tr[ls].maxn,tr[rs].maxn);
}
void build(int u,int l,int r){
    tr[u]=(_){0,0,-1};
    if(l==r) return;
    int mid=l+r>>1;
    build(ls,l,mid); build(rs,mid+1,r);
}
void change(int u,int l,int r,int x,int y,LL h){
    if(h<tr[u].minn) return;
    if(x<=l&&r<=y&&h>=tr[u].maxn){
      ans+=r-l+1;
      tr[u].maxn=tr[u].minn=tr[u].lazy=h;
      return;
    }
    pushdown(u); int mid=l+r>>1;
    if(x<=mid) change(ls,l,mid,x,y,h);
    if(y>mid) change(rs,mid+1,r,x,y,h);
    pushup(u);
}
void miku(){
    ans=0;
    int n,L,R,H; read(n);
    build(1,1,ru);
    for(int i=1;i<=n;i++){
      read(L,R,H); change(1,1,ru,L,R-1,H);
    }
    printf("%lld\n",ans);
}
int main(){
    int T; read(T); 
    while(T--) miku(); 
    return 0;
} 
/*
input:
1
3
5 11 3
1 10 1
3 13 2
0

output: 
14
*/