• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			POJ 3277 City Horizon
		
            
		
              1/*
              2POJ 3277 City Horizon
              3
              4
              5----問題描述：
              6
              7Farmer John has taken his cows on a trip to the city!
              8As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.
              9The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings.
             10Building i's silhouette has a base that spans locations Ai through Bi 
             11along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000)
             12and has height Hi (1 ≤ Hi ≤ 1,000,000,000).
             13Determine the area, in square units, of the aggregate silhouette formed by all N buildings.
             14
             15
             16----輸入：
             17
             18Line 1: A single integer: N 
             19Lines 2..N+1: Input line i+1 describes building i with three space-separated integers: Ai, Bi, and Hi
             20
             21
             22----輸出：
             23
             24Line 1: The total area, in square units, of the silhouettes formed by all N buildings
             25
             26
             27----樣例輸入：
             28
             294
             302 5 1
             319 10 4
             326 8 2
             334 6 3
             34
             35
             36----樣例輸出：
             37
             3816
             39
             40
             41----分析：
             42
             43線段樹+離散化。
             44
             45
             46*/
             47
             48
             49/******************************************************
             50AC 766MS
             51*/
             52
             53#include <iostream>
             54#include <algorithm>
             55
             56using namespace std;
             57
             58typedef  long long  Lint;
             59
             60
             61template<class T, unsigned int N>
             62class CSegTree
             63{
             64public : 
             65        void init( int loc[], int b, int e ){
             66                this->loc = loc;
             67                init( 1, b, e );
             68        }
             69        void modify( int b, int e, int h ){
             70                begin = b;
             71                end   = e;
             72                hei   = h;
             73                modify( 1 );
             74        }
             75        T query( void ){
             76                return query( 1 );
             77        }
             78
             79private : 
             80        void init( int node, int b, int e ){
             81                left[ node ]   = b;
             82                right[ node ]  = e;
             83                height[ node ] = 0;
             84                if( b + 1 < e ){
             85                        init( node << 1, b, ( b + e ) >> 1 );
             86                        init( ( node << 1 ) + 1, ( b + e ) >> 1, e );
             87                }
             88        }
             89        void modify( int node ){
             90                if( ( end <= left[ node ] ) || ( right[ node ] <= begin ) ){
             91                        return;
             92                }
             93                if( ( begin <= left[ node ] ) && ( right[ node ] <= end ) ){
             94                        height[ node ] = max( height[node], hei );
             95                        return;
             96                }
             97                if ( left[ node ] + 1 >= right[ node ] ) {
             98                        return;
             99                }
            100
            101                height[   node << 1 ]       = max( height[ node << 1 ],         height[ node ] );
            102                height[ ( node << 1 ) + 1 ] = max( height[ ( node << 1 ) + 1 ], height[ node ] );
            103                height[ node ] = 0;
            104
            105                modify( node << 1 );
            106                modify( ( node << 1 ) + 1 );
            107        }
            108        T query( int node ){
            109                if( height[ node ] ){
            110                        return ((T)(height[node])) * (((T)(loc[right[node]])) - loc[left[node]]);
            111                }
            112                if( left[ node ] + 1 >= right[ node ] ){
            113                        return 0;
            114                }
            115                return query( node << 1 ) + query( ( node << 1 ) + 1 );
            116        }
            117
            118        typedef int IA[ N * 4 ];
            119        IA  left, right, height;
            120        int *loc;
            121
            122        int begin, end, hei;
            123}            ;
            124
            125template<class T, unsigned int N, unsigned int NT>
            126class CLine
            127{
            128public : 
            129        friend istream & operator>>( istream & is, CLine<T, N, NT> & li ){
            130                is >> li.n;
            131                for( int i = 1; i <= li.n; ++i ){
            132                        is >> li.left[ i ] >> li.right[ i ] >> li.height[ i ];
            133                }
            134                return is;
            135        }
            136        void init_tree( CSegTree<T, NT> & tree ){
            137                int i, j;
            138                n2 = n << 1;
            139                for( j = i = 1; i <= n; ++i,++j ){
            140                        line[ j ].p     = left[ i ];
            141                        line[ j ].id    = i;
            142                        line[ j ].bLeft = 1;
            143
            144                        ++j;
            145                        line[ j ].p     = right[ i ];
            146                        line[ j ].id    = i;
            147                        line[ j ].bLeft = 0;
            148                }
            149                sort( line + 1, line + n2 + 1 );
            150                tp = 0;
            151                line[ 0 ].p = -123456;
            152                for( i = 1; i <= n2; ++i ){
            153                        if( line[ i ].bLeft ){
            154                                left[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
            155                        }
            156                        else{
            157                                right[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
            158                        }
            159                        loc[ tp ] = line[ i ].p;
            160                }
            161
            162                for ( i = 1; i <= n; ++i ) {
            163                        line[ i ].p     = height[ i ];
            164                        line[ i ].id    = left[ i ];
            165                        line[ i ].bLeft = right[ i ];
            166                }
            167                sort( line+1, line+n+1 );
            168                for ( i = 1; i <= n; ++i ) {
            169                        height[ i ] = line[ i ].p;
            170                        left[ i ]   = line[ i ].id;
            171                        right[ i ]  = line[ i ].bLeft;
            172                }
            173
            174                tree.init( loc, 1, tp );
            175                for( i = 1; i <= n; ++i ){
            176                        tree.modify( left[ i ], right[ i ], height[ i ] );
            177                }
            178        }
            179
            180private : 
            181        struct SLine
            182        {
            183                bool operator<( const SLine & b ){
            184                        return p < b.p;
            185                }
            186                int  p, id, bLeft;
            187        }            ;
            188        SLine  line[ N * 2 ];
            189        int    left[ N ], right[ N ], height[ N ], loc[ N * 2 ], n, n2, tp;
            190}            ;
            191
            192const int L = 40009, TL = L * 2;
            193CSegTree<Lint, TL> tree;
            194CLine<Lint, L, TL> line;
            195
            196int main(){
            197        cin >> line;
            198        line.init_tree( tree );
            199        cout << tree.query() << endl;
            200        return 0;
            201}
            202
            
		
            
			posted on 2012-04-22 22:52 coreBugZJ 閱讀(616) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久久久久久99精品免费观看|
精品久久久久久无码中文字幕
|
久久99这里只有精品国产|
大香网伊人久久综合网2020|
精品国产青草久久久久福利|
久久电影网|
久久国产精品77777|
久久精品亚洲欧美日韩久久|
久久久久波多野结衣高潮|
99久久超碰中文字幕伊人|
久久亚洲国产精品123区|
精品综合久久久久久888蜜芽|
久久青青草原精品国产不卡|
亚洲伊人久久精品影院|
精品人妻伦一二三区久久|
久久无码人妻一区二区三区|
色综合久久中文字幕综合网|
2020久久精品国产免费|
久久99热这里只有精品国产|
国产亚洲精久久久久久无码AV|
97久久国产露脸精品国产|
精品久久久久久无码国产|
国产成人精品久久二区二区|
亚洲精品高清国产一线久久|
国产精品久久久香蕉|
日本久久中文字幕|
久久久噜噜噜久久中文字幕色伊伊|
日本久久久久亚洲中字幕|
亚洲欧洲精品成人久久曰影片|
久久精品国产精品国产精品污
|
久久r热这里有精品视频|
亚洲精品乱码久久久久久按摩
|
青青青伊人色综合久久|
久久精品国产亚洲AV无码麻豆|
伊人久久大香线蕉成人|
婷婷久久综合九色综合九七|
久久久久噜噜噜亚洲熟女综合|
国产成人99久久亚洲综合精品
|
久久久老熟女一区二区三区|
久久午夜福利无码1000合集|
久久亚洲精品国产精品婷婷|