uva 1232 SKYLINE

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意:有点纠结,说的是轮廓线。按顺序加入这些建筑,然后看水平方向的轮廓线,如果当前建筑有某段轮廓线的高度>=之前的,就计算这部分的长度。算出每个建筑的值,再累加就是最后的答案。

没加入一段水平线段,就相当于用这段线段去覆盖一个区间,这个线段有权值就是它的高度,如果它去覆盖一个区间,这个区间之前覆盖的权值大于自己,那么该区间的覆盖权值还是保持大的那个值,这个部分不能计算,如果这个线段的权值大于区间的权值,就可以更新区间的权值并且计算这个线段的长度

这题,我把updata写在了query里面,因为如果重新updata,居然超时,可能是我写得不好吧…….

如果可以考虑一下,每次query完,直接就下去updata,是正确的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define MAX 99999
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n,lp[N],rp[N],h[N];
struct SegTree{
int l,r,Max,lazy;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r; Max = 0; lazy = 1;
}
int mid(){
return (l+r) >> 1;
}
}t[N<<2];

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void PushDown(int rt){
if(t[rt].lazy == 0) return ;
t[lson(rt)].Max = t[rson(rt)].Max = t[rt].Max;
t[rt].lazy = 0;
}


void updata(int rt,int a,int b,int height){
if(t[rt].l == a && t[rt].r == b && t[rt].lazy){
if(height > t[rt].Max)
t[rt].Max = height;
return ;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
updata(lson(rt),a,b,height);
else if(a > mid)
updata(rson(rt),a,b,height);
else{
updata(lson(rt),a,mid,height);
updata(rson(rt),mid+1,b,height);
}
}

int query(int rt,int a,int b,int height){
if(t[rt].lazy){
if(t[rt].Max <= height){
updata(rt,a,b,height);
return b-a+1;
}
else
return 0;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
return query(lson(rt),a,b,height);
else if(a > mid)
return query(rson(rt),a,b,height);
else{
int res1 = query(lson(rt),a,mid,height);
int res2 = query(rson(rt),mid+1,b,height);
return res1 + res2;
}
}

int main(){
int cas,n;
scanf("%d",&cas);
while(scanf("%d",&n)!=EOF && n){
int ans = 0;
build(1,1,MAX);
for(int i = 0; i < n; i++){
scanf("%d%d%d",&lp[i],&rp[i],&h[i]);
rp[i]--;
int res = query(1,lp[i],rp[i],h[i]);
ans += res;
}
printf("%d\n",ans);
}
return 0;
}