首页 > 代码库 > SKYLINE

SKYLINE

2024-07-11 22:14:34   214人阅读

uvalive4108:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2109

题意：按照顺序建造一些矩形的房屋，房屋是二维的，每个房屋起点，终点，以及高度给出，然后问你在建造的过程中，所有在建造时候没有被覆盖房屋长度之和。

题解：显然，题目扥意思就是在建造房屋i的时候，在区间x1---x2 之间，比y小或者等于的距离长度。这里就可以用线段树维护。但是要注意，对于此题，要用lazy标记。

lazy==1表示该区间已经被完全覆盖。那么某区间更新的条件就是，1该区间是被完全覆盖的区间，只有一个区间内高度是一致的，才能进行接下来的判断2就是该区间的高度要小于要更新的区间，如果小于则更新，否则直接return。如果不满足条件1，则pushdown()；因为只有当lazy==1才被更新，所以这一题在更新的时候不用做标记。lazy的变化，是在pushdown()里面。还有一个重要的地方就是，本题更新的是线段，要处理这个这个问题，别人的做法就是把右端点-1，其实，想想也是有道理的。还有查询的时候，有点变化，可以把更新直接放在查询里面。只要改区间是完全覆盖的，并且要查询的区间在这个范围内，且小于y值，可以直接返回结果，如果大于，直接返回0，如果区间不是完全覆盖，则pushdown。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100002; 7  8 struct Segtree{ 9    int l,r;10    int mul,lazy;11    inline int mid(){12       return (l+r)/2;13    }14 }num[N*4];15 void build(int rt,int l,int r){16     num[rt].l=l;17     num[rt].r=r;18     num[rt].mul=0;19     num[rt].lazy=1;20     if(l==r)21         return;22     int mid=num[rt].mid();23     build(rt<<1,l,mid);24     build(rt<<1|1,mid+1,r);25 }26 27 void pushdown(int rt){28   if(num[rt].lazy==1){29     num[rt<<1].mul=num[rt].mul;30     num[rt<<1|1].mul=num[rt].mul;31     num[rt].lazy=0;32   }33 }34 void update(int rt,int l,int r,int val){35     if(num[rt].l==l&&num[rt].r==r&&num[rt].lazy==1){36         if(num[rt].mul<val)37             num[rt].mul=val;38             return;39     }40      pushdown(rt);41     int mid=num[rt].mid();42     if(mid>=r)update(rt<<1,l,r,val);43     else if(mid<l)update(rt<<1|1,l,r,val);44     else{45         update(rt<<1,l,mid,val);46         update(rt<<1|1,mid+1,r,val);47     }48 }49 int query(int rt,int l,int r,int val){50     if(num[rt].lazy==1){51         if(num[rt].mul<=val){52            update(rt,l,r,val);53             return r-l+1;54         }55         else return 0;56     }57     pushdown(rt);58     int mid=num[rt].mid();59     if(mid>=r)return query(rt<<1,l,r,val);60     else if(mid<l)return query(rt<<1|1,l,r,val);61     else{62         return query(rt<<1,l,mid,val)+query(rt<<1|1,mid+1,r,val);63     }64 }65 int n;66 int main(){67     int cas,t1,t2,t3;68     scanf("%d",&cas);69     while(cas--){70       scanf("%d",&n);71        build(1,1,100000);72       int ans=0;73       for(int i=1;i<=n;i++){74         scanf("%d%d%d",&t1,&t2,&t3);75         ans+=query(1,t1,t2-1,t3);76       }77       printf("%d\n",ans);78      // scanf("%d",&t1);79     }80 }
View Code

 


联系
我们