• <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 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久精品国产国产精品四凭|
久久久久av无码免费网|
久久精品国产精品青草|
99久久国产综合精品五月天喷水|
国产综合免费精品久久久|
久久久WWW成人免费毛片|
亚洲人成无码网站久久99热国产
|
国产午夜电影久久|
久久99久久无码毛片一区二区
|
久久热这里只有精品在线观看|
97久久国产综合精品女不卡|
精品少妇人妻av无码久久|
久久狠狠一本精品综合网|
久久久噜噜噜久久中文字幕色伊伊
|
97久久精品无码一区二区|
久久亚洲精品无码播放|
久久一日本道色综合久久|
久久97久久97精品免视看|
精品乱码久久久久久久|
久久精品国产AV一区二区三区
|
久久最近最新中文字幕大全|
四虎久久影院|
国产精品久久网|
无码人妻少妇久久中文字幕蜜桃|
国产精品免费久久久久久久久|
亚洲成色WWW久久网站|
国产精品久久久久久久久软件
|
欧洲人妻丰满av无码久久不卡|
亚洲伊人久久综合中文成人网|
a高清免费毛片久久|
久久99精品久久久久久动态图|
伊人久久大香线蕉综合5g|
99久久精品国产综合一区|
国产亚洲精久久久久久无码|
99久久国产宗和精品1上映|
久久香综合精品久久伊人|
狠狠色丁香久久婷婷综合_中
|
青青草国产97免久久费观看|
久久精品三级视频|
久久精品成人免费观看97|
久久人人爽人爽人人爽av|