• <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 閱讀(608) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



99久久人妻无码精品系列|
久久无码一区二区三区少妇|
午夜精品久久久久久中宇|
热re99久久6国产精品免费|
91精品国产高清91久久久久久|
久久精品国产免费一区|
久久婷婷五月综合成人D啪|
思思久久99热只有频精品66|
精品无码久久久久国产|
亚洲一区二区三区日本久久九|
亚洲人成无码www久久久|
久久亚洲中文字幕精品有坂深雪
|
亚洲国产精品久久|
一本一道久久a久久精品综合|
久久精品国产第一区二区三区|
久久国产福利免费|
无码精品久久久天天影视|
国产高潮国产高潮久久久91|
一本色道久久88精品综合|
精品久久久久久国产免费了|
精品久久久久香蕉网|
亚洲国产精品无码久久久久久曰|
午夜精品久久久久久99热|
久久免费视频6|
久久久青草青青国产亚洲免观
|
国产精品99久久久久久www|
热re99久久6国产精品免费|
中文字幕无码久久人妻|
久久e热在这里只有国产中文精品99
|
国产精品亚洲综合久久|
爱做久久久久久|
久久夜色tv网站|
亚洲欧美日韩精品久久|
国产精品久久久久jk制服|
久久天天躁夜夜躁狠狠躁2022|
久久不见久久见免费影院www日本|
国内精品久久久久影院一蜜桃|
新狼窝色AV性久久久久久|
亚洲午夜久久久久久久久电影网
|
新狼窝色AV性久久久久久|
久久中文字幕人妻丝袜|