题目传送门
天际线
题目大意
在二维坐标系的第一象限中，x轴上有多个城市，分别给你每个高楼的起始点，高度和终止点，高楼可以重叠，求高楼的总轮廓，输出为每个折点的（x，y）
思路
做法：扫描线+线段树做线段区间覆盖 数据范围不大，所以可以不离散化 直接线段树维护区间最大值即可
AC Code
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e4+7;
int t
[N
<<2],tag
[N
<<2];
inline int lc(int p
) {return p
<<1;}
inline int rc(int p
) {return p
<<1|1;}
inline void push_up(int p
) {t
[p
]=max(t
[lc(p
)], t
[rc(p
)]);}
inline void f(int p
, int k
){
t
[p
]=max(t
[p
], k
);
tag
[p
]=max(tag
[p
], k
);
}
inline void push_down(int p
){
f(lc(p
), tag
[p
]);
f(rc(p
), tag
[p
]);
tag
[p
]=0;
}
inline void updata(int p
, int l
, int r
, int x
, int y
, int k
){
if(x
>r
|| y
<l
) return ;
if(l
<=x
&& y
<=r
){
t
[p
]=max(t
[p
],k
);
tag
[p
]=max(tag
[p
],k
);
return ;
}
int mid
=(x
+y
)>>1;
if(tag
[p
]) push_down(p
);
updata(lc(p
), l
, r
, x
, mid
, k
);
updata(rc(p
), l
, r
, mid
+1, y
, k
);
push_up(p
);
}
inline int query(int p
, int l
, int r
, int x
, int y
){
if(x
>r
|| y
<l
) return 0;
if(l
<=x
&& y
<=r
) return t
[p
];
int mid
=(x
+y
)>>1;
if(tag
[p
]) push_down(p
);
return max(query(lc(p
), l
, r
, x
, mid
), query(rc(p
), l
, r
, mid
+1, y
));
}
int n
,h
[N
];
int x
,y
,z
;
int main() {
while(~scanf("%d%d%d",&x
, &y
, &z
)) updata(1,x
,z
-1,1,N
,y
);
for(int i
=1;i
<=N
;++i
) h
[i
] = query(1,i
,i
,1,N
);
for(int i
=1;i
<=N
;++i
) if(h
[i
] != h
[i
-1]) printf("%d %d ",i
,h
[i
]);
return 0;
}
