• <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 極限定律 閱讀(915) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲精品乱码久久久久66| 久久综合国产乱子伦精品免费| 99久久精品国产一区二区蜜芽| 国产精品久久久久久久久| 99久久免费只有精品国产| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 污污内射久久一区二区欧美日韩| 亚洲精品国产字幕久久不卡| 久久久久久国产精品美女| 无码国内精品久久人妻| 中文精品久久久久国产网址| 无码任你躁久久久久久久| 久久精品99久久香蕉国产色戒| 91久久成人免费| 狠狠综合久久AV一区二区三区| 精品久久久久久国产| 一本色道久久88综合日韩精品 | 狠狠精品久久久无码中文字幕| 久久中文娱乐网| 色综合久久综合中文综合网| 久久男人中文字幕资源站| 久久精品国产久精国产思思| 一级女性全黄久久生活片免费| 伊人久久大香线蕉影院95| 人妻精品久久无码区| 中文字幕久久久久人妻| 亚洲欧洲久久av| 日日狠狠久久偷偷色综合96蜜桃 | 久久国产三级无码一区二区 | 久久综合九色综合欧美就去吻| 久久天堂电影网| 日本福利片国产午夜久久| 久久99精品久久久久久| 久久不见久久见免费视频7| 亚洲AV无码一区东京热久久| 精品多毛少妇人妻AV免费久久| 亚洲精品乱码久久久久久蜜桃 | 亚洲国产成人精品91久久久 | 国内精品久久久久影院老司| 热久久国产欧美一区二区精品| 国产精品免费久久久久影院|