[POJ]3277.City Horizon

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

分析

由题意可以知道，这道题需要求的即是这些矩形的面积并。考虑到题目中一个特殊的条件，所有的矩形的一边在一条直线上，我们可以好好利用这个条件：由于所有的矩形在这条直线上的投影均与矩形的一个边长相等。所以，我们可以把矩形“压缩”成直线上的线段，且每条线段都有一个权值，这个权值就是矩形的高度Hi。那么，我们就可以利用线段树进行处理，计算面积并就相当于计算带权的线段并，即S = H * (B – A)。当某条线段被多次覆盖时（比如图中的线段A2B1），只取H值最大的进行计算。如图2.1中的矩形面积并为：S = H1*(B1 – A1) + H2 * (A3 – B2) + H3 * (B3 – A3) 基本思路清楚了，我们现在来考虑具体实现。

由于题目中矩形的左右坐标的范围非常大(1 <= Ai,Bi <= 10^9)，如果建立大小为[1, 10^9)的线段树则会占用大量的空间。我们采用一种离散化的思想来处理这个问题，这种思路在线段树的题目中也是经常会用到的。考虑到一共只有N <= 40000个矩形，那么，这些矩形一共也只有2 * 40000 = 80000个左右坐标值。我们首先将这80000个坐标值按大小排序，对排序后的坐标依次赋予一个新坐标值k（1 <= k <= 80000），这样我们就把长度为[1, 10^9)的线段离散化成[1,80000)的线段了，而最后计算结果时，只需要按照新坐标值找回原始坐标值并代入计算即可。

举一个简单的例子，假设现在有三条线段[20,60),[10,50),[5,55)。我们将这三条线段的左右端点进行排序，其结果为5,10,20,50,55,60。我们将它们依次赋上新值1,2,3,4,5, 6。这样原始的三条线段被离散化为[3,6),[2,4),[1,5)，我们就可以在[1,6)的空间内对其进行处理了。这就是离散化的威力。

回到原问题上来，当矩形所投影的线段被离散化以后，我们就可以建立线段树了。与之前讲过的初始化略有不同，现在每个线段树的节点不只是记录其所代表的线段是否被覆盖，而且要记录被覆盖的线段的权值。每次加入一个矩形就是在线段树上插入一条带权的线段，插入的实现过程与之前的也有不同。如果当前线段完全覆盖了节点所代表的线段，那么比较这两个线段的权值大小。如果节点所代表的线段的权值小或者在之前根本未被覆盖，则将其权值更新为当前线段的权值。

// 插入
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);
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>