• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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

                題目的意思是說:平面上有[1,40000]個建筑,每個建筑有一個區間[Ai,Bi]表示它的跨度,Hi表示其高度。要求這n個建筑的平面覆蓋面積。
            由于Ai,Bi∈[1,1000000000],直接將線段[Ai,Bi]插入線段樹空間消耗太大,可以將這n條線段的2n個端點離散化到一個數組X[0...2n-1],然后再將其插入線段樹,最后求出面積。
            #include <iostream>
            using namespace std;

            const int MAXN = 40010;
            struct segment{
                
            int left,right,h;
            }
            tree[MAXN*3];
            int pos[MAXN][3],x[MAXN*2],len;

            int cmp1(const void *a,const void *b){
                
            return *(int *)a-*(int *)b;
            }

            int cmp2(const void *a,const void *b){
                
            return *((int *)a+2)-*((int *)b+2);
            }

            int query(int h){
                
            int low=0,high=len-1,mid;
                
            while(low<=high){
                    mid
            =(low+high)>>1;
                    
            if(x[mid]==h) return mid;
                    
            else if(x[mid]>h) high=mid-1;
                    
            else low=mid+1;
                }

                
            return -1;
            }

            void create(int l,int r,int index){
                tree[index].left
            =l,tree[index].right=r;
                tree[index].h
            =0;
                
            if(r==l+1return;
                
            int mid=(l+r)>>1;
                create(l,mid,
            2*index);
                create(mid,r,
            2*index+1);
            }

            void update(int l,int r,int h,int index){
                
            if(h<tree[index].h) return;
                
            if(l==tree[index].left && r==tree[index].right){
                    tree[index].h
            =h;
                    
            return;
                }

                
            if(tree[index].h>=0 && tree[index].right>tree[index].left+1){
                    tree[
            2*index].h=tree[2*index+1].h=tree[index].h;
                    tree[index].h
            =-1;
                }

                
            int mid=(tree[index].left+tree[index].right)>>1;
                
            if(r<=mid)
                    update(l,r,h,
            2*index);
                
            else if(l>=mid)
                    update(l,r,h,
            2*index+1);
                
            else{
                    update(l,mid,h,
            2*index);
                    update(mid,r,h,
            2*index+1);
                }

            }

            long long cal(int index){
                
            if(tree[index].h>=0)
                    
            return tree[index].h*(long long)(x[tree[index].right]-x[tree[index].left]);
                
            else
                    
            return cal(2*index)+cal(2*index+1);
            }

            int main(){
                
            int n,i,k,l,r;
                scanf(
            "%d",&n);
                
            for(i=len=0;i<n;i++,len+=2){
                    scanf(
            "%d %d %d",&pos[i][0],&pos[i][1],&pos[i][2]);
                    x[len]
            =pos[i][0],x[len+1]=pos[i][1];
                }

                qsort(x,
            2*n,sizeof(int),cmp1);
                
            for(i=1,k=0;i<2*n;i++)
                    
            if(x[i]!=x[i-1]) x[k++]=x[i-1];
                x[k
            ++]=x[i-1],len=k;
                qsort(pos,n,
            3*sizeof(int),cmp2);
                create(
            0,len-1,1);
                
            for(i=0;i<n;i++){
                    l
            =query(pos[i][0]),r=query(pos[i][1]);
                    update(l,r,pos[i][
            2],1);
                }

                printf(
            "%I64d\n",cal(1));
                
            return 0;
            }

            posted on 2009-05-13 15:50 極限定律 閱讀(913) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品一本到99热免费| 亚洲精品tv久久久久久久久久| 亚洲欧美成人综合久久久| 亚洲午夜久久久影院| 久久久久久久99精品免费观看| 国产成人精品久久亚洲| 久久这里都是精品| AAA级久久久精品无码片| 国产AV影片久久久久久| 99久久国产亚洲综合精品| 国产成人精品久久免费动漫| 伊人情人综合成人久久网小说 | 久久亚洲中文字幕精品有坂深雪| 伊人久久综在合线亚洲2019| 久久亚洲国产成人影院| 国产成人无码精品久久久免费| 久久这里有精品| 久久强奷乱码老熟女| 久久久久久久综合日本亚洲| 久久综合给久久狠狠97色| 久久亚洲中文字幕精品一区| 久久99精品国产| 99精品国产在热久久无毒不卡 | 久久99久久99精品免视看动漫 | 欧美精品丝袜久久久中文字幕| 精品国产一区二区三区久久久狼| 四虎影视久久久免费| 精品久久久久久久久久久久久久久 | 久久久亚洲欧洲日产国码aⅴ| 婷婷久久综合| 久久久精品视频免费观看| 久久久久久狠狠丁香| 久久综合狠狠综合久久激情 | 久久久久亚洲av无码专区导航 | 91久久香蕉国产熟女线看| 久久精品国产99国产电影网| av国内精品久久久久影院| 国产精品视频久久| 亚洲国产精品热久久| 久久精品国产福利国产琪琪| 亚洲午夜精品久久久久久浪潮|