【Bzoj1645】City Horizon城市地平线

来源和评测点

USACO 2007 Open Silver
Bzoj1645

题目

【题目大意】
约翰带着奶牛去都市观光。在落日的余晖里,
他们看到了一幢接一幢的摩天高楼的轮廓在地平线上形成美丽的图案。
以地平线为 X 轴,每幢高楼的轮廓是一个位于地平线上的矩形,
彼此间可能有重叠的部分。
奶牛一共看到了N幢高楼,第i幢楼的高度是Hi,
两条边界轮廓在地平线上的坐标是Ai到Bi。
请帮助奶牛们计算一下,所有摩天高楼的轮廓覆盖的总面积是多少。
【输入格式】
第一行:单个整数N,1≤N≤40000
第二行到第N+1行:第i+1行有三个整数Ai,Bi和Hi,1≤Ai<Bi≤10^9, 1≤Hi≤10^9
【输出格式】
单个整数:表示摩天高楼轮廓所覆盖的总面积
【输入样例】
4
2 5 1
9 10 4
6 8 2
4 6 3
【输出样例】
16
【样例解释】
只有第一幢楼和最后一幢楼有1个单位的重叠面积

分析

线段树教程和题目分类参见:
【OI之路】06树-1线段树
其他线段树题目参见:Tag-线段树

我看到网上有说“扫描线”,并不知道是什么……
反正我的做法就是离散化信息,
然后使用线段树,区间修改,维护单点最值
最后求和即可

具体可参考注释

代码

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
93
94
95
96
97
98
99
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymax(int x,int y) {return x>y?x:y;}
typedef long long ll;
struct seg
{
int l,r,mid;
int lc,rc;
int mx,lz;
}p[200000];
int ln;
int build(int l,int r)
{
int t=++ln;
p[t].l=l;p[t].r=r;p[t].mid=(l+r)>>1;
if(l<r)
{
p[t].lc=build(l,p[t].mid);
p[t].rc=build(p[t].mid+1,r);
}
return t;
}
//lz是lazy优化(区间修改一般都有)
//定义为某尚未尝试更新的值,且必须下传
void pushdown(int x)
{
if(!p[x].lz) return;
p[x].mx=mymax(p[x].mx,p[x].lz);
int lc=p[x].lc,rc=p[x].rc;
p[lc].lz=mymax(p[lc].lz,p[x].lz);
p[rc].lz=mymax(p[rc].lz,p[x].lz);
p[x].lz=0;
}
void change(int x,int l,int r,int c)
{
if(p[x].l==l and p[x].r==r)
{
p[x].lz=mymax(p[x].lz,c);
return;
}
pushdown(x);
int lc=p[x].lc,rc=p[x].rc;
if(r<=p[x].mid) change(lc,l,r,c);
else if(l>p[x].mid) change(rc,l,r,c);
else change(lc,l,p[x].mid,c),change(rc,p[x].mid+1,r,c);
}
int ask(int w,int x)
{
pushdown(w);
if(p[w].l==p[w].r) return p[w].mx;
if(x<=p[w].mid) return ask(p[w].lc,x);
return ask(p[w].rc,x);
}
int n;
int a[81000];
int l[41000],r[41000],h[41000];
int find(int x)
{
int l=1,r=2*n;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[mid]<x) l=mid+1;
else if(a[mid]==x) return mid;
else r=mid-1;
}
}
//由于是函数,保证了相同x返回相同的值,具体是什么不重要
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&l[i],&r[i],&h[i]);
if(l[i]==r[i])//特判,防止空信息
{
i--;n--;
continue;
}
a[2*i-1]=l[i];a[2*i]=r[i];
}
sort(a+1,a+1+2*n);
int rx=2*n;
//改点区间为段区间,便于维护
ln=0;build(1,rx);
for(int i=1;i<=n;i++)
change(1,find(l[i])+1,find(r[i]),h[i]);
//二分离散化
//为了能够实现同值的结果依然同值并且获得损失的区间信息量
ll s=0;
for(int i=2;i<=2*n;i++)
s+=ll(ask(1,i))*ll(a[i]-a[i-1]);
//记得还原信息
printf("%lld",s);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/eed1.html
转载请注明出处,谢谢!