Description
Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.
The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings. Building i’s silhouette has a base that spans locations Ai through Bi along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000) and has height Hi (1 ≤ Hi ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.
Input
Line 1: A single integer: N
Lines 2..N+1: Input line i+1 describes building i with three space-separated integers: Ai, Bi, and Hi
Output
Line 1: The total area, in square units, of the silhouettes formed by all N buildings
Sample Input
4
2 5 1
9 10 4
6 8 2
4 6 3
Sample Output
16
Hint
The first building overlaps with the fourth building for an area of 1 square unit, so the total area is just 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.
Source
USACO 2007 Open Silver
題目大意
如圖所示，在一條水平線上有N個建築物，建築物都是長方形的，且可以互相遮蓋。給出每個建築物的左右坐標值Ai,Bi以及每個建築物的高Hi，需要計算出這些建築物總共覆蓋的面積。
題目數據范圍：
建築物個數N：1 <= N <= 40000
建築物左右坐標值Ai, Bi：1 <= Ai,Bi <= 10^9
建築物的高度Hi：1 <= Hi <= 10^9
vczixL/W0NK7uPbM2MritcTM9bz+o6zL+dPQtcS+2NDOtcTSu7Hf1NrSu8z11rHP38nPo6zO0sPHv8nS1LrDusPA+9PD1eK49sz1vP6jutPJ09rL+dPQtcS+2NDO1NrV4sz11rHP38nPtcTNttOwvvnT677Y0M61xNK7uPax37Okz+C1yKGjy/nS1KOsztLDx7/J0tSw0b7Y0M6hsNG5y/WhsbPJPHN0cm9uZz7Wsc/fyc+1xM/fts48L3N0cm9uZz6jrMfSw7/M9c/fts62vNPQ0ru49jxzdHJvbmc+yKjWtTwvc3Ryb25nPqOs1eK49sio1rW+zcrHvtjQzrXEuN+2yEhpoaPEx8O0o6zO0sPHvs2/ydLUwPvTw8/fts7K97340NC0psDto6y8xsvjw+a7/bKivs3P4LWx09q8xsvjtPjIqLXEz9+2zrKio6y8tFMgPSBIICogKEIgqEMgQSmho7WxxLPM9c/fts6xu7bgtM64srjHyrGjqLHIyOfNvNbQtcTP37bOQTJCMaOpo6zWu8ihSNa11+6087XEvfjQ0LzGy+Oho8jnzbwyLjHW0LXEvtjQzsPmu/2yos6qo7pTID0gSDEqKEIxIKhDIEExKSArIEgyICogKEEzIKhDIEIyKSArIEgzICogKEIzIKhDIEEzKSC7+bG+y7zCt8fls/7By6OsztLDx8/W1NrAtL+8wse+38zlyrXP1qGjPC9wPgoKPHA+08nT2szixL/W0L7Y0M61xNfz09LX+LHqtcS3ts6nt8ezo7TzKDEgPD0gQWksQmkgPD0gMTBeOSmjrMjnufu9qMGitPPQoc6qWzEsIDEwXjkptcTP37bOyvfU8rvh1bzTw7Tzwb+1xL/VvOSho87Sw8eyydPD0rvW1jxzdHJvbmc+wOvJoruvPC9zdHJvbmc+tcTLvM/rwLS0psDt1eK49s7KzOKjrNXi1tbLvMK31NrP37bOyve1xMzixL/W0NKyyse+rbOju+HTw7W9tcSho7+8wse1vdK7ubLWu9PQTiA8PSA0MDAwMLj2vtjQzqOsxMfDtKOs1eLQqb7Y0M7Su7my0rLWu9PQMiAqIDQwMDAwID0gODAwMDC49tfz09LX+LHq1rWho87Sw8fK18/IvavV4jgwMDAwuPbX+LHq1rWwtLTz0KHFxdDyo6y21MXF0PK687XE1/ix6tLAtM64s9Po0ru49tDC1/ix6ta1a6OoMSA8PSBrIDw9IDgwMDAwo6mjrNXi0fnO0sPHvs2w0bOktsjOqlsxLCAxMF45KbXEz9+2zsDryaK7r7PJWzEsODAwMDAptcTP37bOwcujrLb41+6687zGy+O94bn7yrGjrNa70OjSqrC01dXQwtf4serWtdXSu9jUrcq81/ix6ta1sqK0+sjrvMbL47y0v8mhozwvcD4KCjxwPr7Z0ru49rzytaW1xMD919OjrLzZyejP1tTa09DI/cz1z9+2zlsyMCw2MCksWzEwLDUwKSxbNSw1NSmho87Sw8e9q9XiyP3M9c/fts61xNfz09K2y7XjvfjQ0MXF0PKjrMbkveG5+86qNSwxMCwyMCw1MCw1NSw2MKGjztLDx72ry/zDx9LAtM64s8nP0MLWtTEsMiwzLDQsNSwgNqGj1eLR+dStyry1xMj9zPXP37bOsbvA68miu6/OqlszLDYpLFsyLDQpLFsxLDUpo6zO0sPHvs2/ydLU1NpbMSw2KbXEv9W85MTattTG5L340NC0psDtwcuho9Xivs3Kx8DryaK7r7XEzf7BpqGjPC9wPgoKPHA+u9i1vdStzsrM4snPwLSjrLWxvtjQzsv5zbbTsLXEz9+2zrG7wOvJoruv0tS686OsztLDx77Nv8nS1L2owaLP37bOyvfBy6Gj0+vWrsewvbK5/bXEs/XKvLuvwtTT0LK7zayjrM/W1NrDv7j2z9+2zsr3tcS92rXjsrvWu8rHvMfCvMbky/m0+rHttcTP37bOyse38bG7uLK4x6OstvjH0tKqvMfCvLG7uLK4x7XEz9+2zrXEyKjWtaGjw7+0zrzTyOvSu7j2vtjQzr7NysfU2s/fts7K98nPsuXI69K7zPW0+MiotcTP37bOo6yy5cjrtcTKtc/Wuf2zzNPr1q7HsLXE0rLT0LK7zayho8jnufu1scewz9+2zs3qyKu4srjHwcu92rXjy/m0+rHttcTP37bOo6zEx8O0sci9z9Xiwb249s/fts61xMio1rW089ChoaPI57n7vdq148v5tPqx7bXEz9+2zrXEyKjWtdChu/LV39Ta1q7HsLj5sb7OtLG7uLK4x6Os1PK9q8bkyKjWtbj80MLOqrWxx7DP37bOtcTIqNa1oaM8L3A+CgoKCjxwcmUgY2xhc3M9"brush:java;">// 插入
void Insert(int left,int right,int height,int num){
// 若插入的線段完全覆蓋當前節點所表示的線段
if(intervalTree[num].left == left && intervalTree[num].right == right){
// 更新權值(高度)
if(intervalTree[num].height < height){
intervalTree[num].height = height;
}//if
intervalTree[num].cover = 1;
return;
}//if
// 當前節點的左子節點所代表的線段包含插入的線段
if(right <= intervalTree[num].mid){
Insert(left,right,height,2*num);
}//if
// 當前節點的右子節點所代表的線段包含插入的線段
else if(left >= intervalTree[num].mid){
Insert(left,right,height,2*num+1);
}//if
// 插入的線段跨越了當前節點所代表線段的中點
else{
Insert(left,intervalTree[num].mid,height,2*num);
Insert(intervalTree[num].mid,right,height,2*num+1);
}//else
}
而最後計算面積並時，需要遍歷整個線段樹，因為這樣才能確定每個從根節點到葉節點的路徑上，即每個元線段上（形如[a,a+1)的線段），最大的高度是多少。統計過程從根向葉遍歷，遍歷過程中統計高度的最大值，並在葉節點上進行計算，非葉節點的計算結果是其左右子節點的計算結果之和。實現的代碼如下(因為計算結果的數據超過了int的范圍，所以使用long long 數據類型):
// 計算面積
long long Cal(int h,int num){
// 統計過程從根向葉遍歷，遍歷過程中統計高度的最大值
if(h > builds[num].height){
builds[num].height = h;
}//if
// 葉節點上進行計算
if(builds[num].left + 1 == builds[num].right){
long long area = builds[num].height *
(hash[builds[num].right] - hash[builds[num].left]);
return area;
}//if
// 非葉節點的計算結果是其左右子節點的計算結果之和
return Cal(builds[num].height,2*num) +
Cal(builds[num].height,2*num+1);
}
