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





            
	    
    




            






            

				

            


    
    







            
	   
	



午夜不卡久久精品无码免费|
69国产成人综合久久精品|
欧美va久久久噜噜噜久久|
无码国内精品久久人妻麻豆按摩|
久久综合久久综合久久综合|
热re99久久精品国99热|
婷婷久久香蕉五月综合加勒比|
精品综合久久久久久97|
免费国产99久久久香蕉|
久久福利青草精品资源站免费
|
99久久99久久精品免费看蜜桃|
亚洲中文久久精品无码|
久久久婷婷五月亚洲97号色|
国产精品美女久久久久|
91超碰碰碰碰久久久久久综合|
国产精品永久久久久久久久久|
久久天天躁狠狠躁夜夜2020老熟妇|
一本久道久久综合狠狠躁AV|
狠狠色丁香久久婷婷综合五月|
久久久久人妻一区二区三区vr
|
91秦先生久久久久久久|
日韩亚洲国产综合久久久|
久久亚洲国产精品成人AV秋霞|
色综合久久久久无码专区|
精品久久久久久中文字幕|
久久AⅤ人妻少妇嫩草影院|
青青草原精品99久久精品66|
91精品国产9l久久久久|
久久综合给久久狠狠97色|
2021久久国自产拍精品|
品成人欧美大片久久国产欧美|
久久综合五月丁香久久激情|
国内高清久久久久久|
久久99热精品|
亚洲色大成网站www久久九
|
色99久久久久高潮综合影院|
亚洲色大成网站WWW久久九九|
久久精品视屏|
国产美女久久久|
亚洲综合精品香蕉久久网|
久久精品综合一区二区三区|