首页 > 代码库 > Uva 1232 - SKYLINE ( 线段树 + 区间更新 )
Uva 1232 - SKYLINE ( 线段树 + 区间更新 )
Uva 1232 SKYLINE （线段树 + 区间更新）
题意： 按照顺序在地面上建造放在，每个房子的高度为h，操作 l r h 表示 在(l,r] 区间建立一个高度为h的房子。
统计每次建立完房子之后的overlap值之和
overlap值表示[ 修完一座房子之后，统计它在多长的部分是最高的(可以和其他房子并列高) ]
如样例图，按照灰、黒。白的顺序建立房子
ans = (11-5) + (5-1) + (5-3) + (13-11) = 6 + 4 + 4 = 14
分析： 一开始一直想不明白如何向下传递，这里实际上Pushdown操作就是普通的懒惰标记
PushUp操作用来想上更新minh和maxh
这里需要维护至少两个域 一个是 房子的高度setv 一个是maxh，区间内房子的最大高度。
不过从别人的博客看到还有一个优化，就是再开一个minh域，存放区间内房子的最小高度，
很显然，如果新建立的房子高度比该区间的minh还小，就不需要更新了。
结果用ans进行累加即可，这里要注意，线段是连续的，但是所以区间(l,r]想当于[l+1,r]
update的时候注意下，还有就是求ans的时候记得+1
//#define BUG#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <vector>#include <list>#include <queue>#include <ctime>#include <iostream>#include <cmath>#include <set>#include <string>using namespace std;typedef long long LL;typedef unsigned long long ULL;#define INF 0x7fffffff#define MAX 0x3f3f3f3f#define CLR( a, b ) memset( a, b, sizeof(a) )#define REP( i, a, b ) for( int i = (a); i < (b); ++i )#define FOR( i, a, b ) for( int i = (a); i <=(b); ++i )#define FOD( i, a, b ) for( int i = (a); i >=(b); --i )#define MID ( l + r ) >> 1#define lson l, m, o << 1#define rson m + 1, r, o << 1 | 1#define ls o << 1#define rs o << 1 | 1#define MAXN 100010struct SegTree{ int l, r; int setv, maxh, minh;}tree[MAXN << 2];int ans;void PushUp( int o ){ tree[o].maxh = max( tree[ls].maxh , tree[rs].maxh ); tree[o].minh = min( tree[ls].minh , tree[rs].minh );}void PushDown( int o ){ if( tree[o].setv != -1 ) //三个标记往下传 { tree[ls].setv = tree[rs].setv = tree[o].setv; tree[ls].maxh = tree[rs].maxh = tree[o].maxh; tree[ls].minh = tree[rs].minh = tree[o].minh; tree[o].setv = -1; }}void Build( int l, int r, int o ){ tree[o].l = l, tree[o].r = r; tree[o].setv = tree[o].maxh = tree[o].minh = 0; if( l == r ) return; int m = MID; Build( lson ); Build( rson );}void Update( int L, int R, int c, int o ){ if( tree[o].minh > c ) return; if( tree[o].l == L && tree[o].r == R ) { if( tree[o].maxh <= c ) { tree[o].setv = tree[o].maxh = tree[o].minh = c; ans += R - L + 1; return; } if( L == R ) return; } PushDown( o ); int m = ( tree[o].l + tree[o].r ) >> 1; if( R <= m ) Update( L, R, c, ls ); else if( L > m ) Update( L, R, c, rs ); else { Update( L, m, c, ls ); Update( m + 1, R, c, rs ); } PushUp( o );}void Orz(){ #ifdef BUG freopen("in.txt","r",stdin); #endif int cas, n; int l, r, c; while( ~scanf( "%d", &cas ) && cas ) { while( cas-- ) { scanf( "%d", &n ); Build(1,MAXN,1); ans = 0; while( n-- ) { scanf( "%d %d %d", &l, & r, &c ); Update( l + 1, r, c, 1); } printf( "%d\n", ans ); } }}int main(){ Orz(); return 0;}
Uva 1232 - SKYLINE ( 线段树 + 区间更新 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。