• <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 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久99这里只有精品国产|
成人久久精品一区二区三区|
99久久无码一区人妻|
94久久国产乱子伦精品免费|
久久精品无码av|
久久精品国产亚洲AV久|
国产午夜免费高清久久影院|
久久99热这里只有精品国产|
欧美激情一区二区久久久|
久久91精品国产91久久麻豆|
久久综合九色欧美综合狠狠
|
99久久免费国产特黄|
国产精品成人精品久久久|
久久精品国产AV一区二区三区|
久久精品国产免费|
精品久久亚洲中文无码|
久久黄视频|
99久久婷婷国产综合亚洲|
少妇久久久久久被弄到高潮
|
久久久久99精品成人片牛牛影视|
亚洲精品国产自在久久|
久久青青草原综合伊人|
老色鬼久久亚洲AV综合|
一级a性色生活片久久无少妇一级婬片免费放
|
精品久久久久久国产三级|
色综合久久中文字幕无码|
久久午夜综合久久|
精品久久久久一区二区三区|
91精品国产91久久久久福利|
无码人妻久久一区二区三区免费
|
91久久成人免费|
91精品国产91久久综合|
久久超碰97人人做人人爱|
亚洲va久久久噜噜噜久久男同|
无码任你躁久久久久久久|
久久精品无码专区免费|
久久最新精品国产|
66精品综合久久久久久久|
国内精品久久久久久99蜜桃|
久久综合精品国产二区无码|
久久亚洲私人国产精品|