• <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 2528 Mayor's posters
		
            
		
              1/*
              2POJ 2528 Mayor's posters
              3
              4
              5----問題描述：
              6
              7The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim.
              8The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules: 
              9Every candidate can place exactly one poster on the wall. 
             10All posters are of the same height equal to the height of the wall;
             11the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
             12The wall is divided into segments and the width of each segment is one byte.
             13Each poster must completely cover a contiguous number of wall segments.
             14
             15They have built a wall 10000000 bytes long (such that there is enough place for all candidates).
             16When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width.
             17Moreover, the candidates started placing their posters on wall segments already occupied by other posters.
             18Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
             19Your task is to find the number of visible posters when all the posters are placed given the information about posters' size,
             20their place and order of placement on the electoral wall.
             21
             22
             23----輸入：
             24
             25The first line of input contains a number c giving the number of cases that follow.
             26The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 , , ri.
             27
             28
             29----輸出：
             30
             31For each input data set print the number of visible posters after all the posters are placed.
             32
             33
             34----樣例輸入：
             35
             361
             375
             381 4
             392 6
             408 10
             413 4
             427 10
             43
             44
             45----樣例輸出：
             46
             474
             48
             49
             50----分析：
             51
             52線段樹。
             53
             54
             55*/
             56
             57
             58
             59#include <iostream>
             60#include <algorithm>
             61
             62using namespace std;
             63
             64template<unsigned int N>
             65class CSegTree
             66{
             67public : 
             68        void init( int b, int e ){
             69                init( 1, b, e );
             70        }
             71        void modify( int b, int e, int d ){
             72                begin = b;
             73                end   = e;
             74                data  = d;
             75                modify( 1 );
             76        }
             77        int query( void ){
             78                memset( visible, 0, sizeof( visible ) );
             79                query( 1 );
             80                data = 0;
             81                for( int i = 1; i < N; ++i ){
             82                        if( visible[ i ] ){
             83                                ++data;
             84                        }
             85                }
             86                return data;
             87        }
             88
             89private : 
             90        void init( int node, int b, int e ){
             91                left[ node ]  = b;
             92                right[ node ] = e;
             93                id[ node ]    = 0;
             94                if( b < e ){
             95                        init( node << 1, b, ( b + e ) >> 1 );
             96                        init( ( node << 1 ) + 1, ( ( b + e ) >> 1 ) + 1, e );
             97                }
             98        }
             99        void modify( int node ){
            100                if( ( end < left[ node ] ) || ( right[ node ] < begin ) ){
            101                        return;
            102                }
            103                if( data == id[ node ] ){
            104                        return;
            105                }
            106                if( ( begin <= left[ node ] ) && ( right[ node ] <= end ) ){
            107                        id[ node ] = data;
            108                        return;
            109                }
            110                if( id[ node ] ){
            111                        id[ node << 1 ] = id[ ( node << 1 ) + 1 ] = id[ node ];
            112                        id[ node ] = 0;
            113                }
            114                modify( node << 1 );
            115                modify( ( node << 1 ) + 1 );
            116                if( id[ node << 1 ] == id[ ( node << 1 ) + 1 ] ){
            117                        id[ node ] = id[ node << 1 ];
            118                }
            119        }
            120        void query( int node ){
            121                if( id[ node ] ){
            122                        visible[ id[ node ] ] = true;
            123                        return;
            124                }
            125                if( left[ node ] >= right[ node ] ){
            126                        return;
            127                }
            128                query( node << 1 );
            129                query( ( node << 1 ) + 1 );
            130        }
            131
            132        enum{ L = N * 3 };
            133        typedef int IA[ L ];
            134        IA left, right, id;
            135        bool visible[ N ];
            136
            137        int begin, end, data;
            138        
            139}            ;
            140
            141template<unsigned int N, unsigned int NT>
            142class CLine
            143{
            144public : 
            145        friend istream & operator>>( istream & is, CLine<N,NT> & li ){
            146                is >> li.n;
            147                for( int i = 1; i <= li.n; ++i ){
            148                        is >> li.left[ i ] >> li.right[ i ];
            149                }
            150                return is;
            151        }
            152        void init_tree( CSegTree<NT> & tree ){
            153                int i, j;
            154                n2 = n << 1;
            155                for( j = i = 1; i <= n; ++i,++j ){
            156                        line[ j ].p     = left[ i ];
            157                        line[ j ].id    = i;
            158                        line[ j ].bLeft = true;
            159
            160                        ++j;
            161                        line[ j ].p     = right[ i ];
            162                        line[ j ].id    = i;
            163                        line[ j ].bLeft = false;
            164                }
            165                sort( line + 1, line + n2 + 1 );
            166                tp = 0;
            167                line[ 0 ].p = -123456;
            168                for( i = 1; i <= n2; ++i ){
            169                        if( line[ i ].bLeft ){
            170                                left[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
            171                        }
            172                        else{
            173                                right[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
            174                        }
            175                }
            176                tree.init( 1, tp );
            177                for( i = 1; i <= n; ++i ){
            178                        tree.modify( left[ i ], right[ i ], i );
            179                }
            180        }
            181
            182private : 
            183        struct SLine
            184        {
            185                bool operator<( const SLine & b ){
            186                        return p < b.p;
            187                }
            188                int  p, id;
            189                bool bLeft;
            190        }            ;
            191        SLine  line[ N * 2 ];
            192        int    left[ N ], right[ N ], n, n2, tp;
            193}            ;
            194
            195const int L = 30009, TL = L * 2;
            196CSegTree<TL> tree;
            197CLine<L,TL> line;
            198
            199int main(){
            200        int td;
            201        cin >> td;
            202        while( td-- ){
            203                cin >> line;
            204                line.init_tree( tree );
            205                cout << tree.query() << endl;
            206        }
            207        return 0;
            208}
            209
            
		
            
			posted on 2012-04-22 22:50 coreBugZJ 閱讀(545) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



99热成人精品免费久久|
久久精品国产亚洲AV不卡|
久久亚洲精品国产亚洲老地址|
久久天天日天天操综合伊人av|
久久久久久亚洲精品影院|
亚洲精品无码久久久久久|
久久精品国产亚洲沈樵|
亚洲欧洲中文日韩久久AV乱码|
久久综合狠狠综合久久|
久久久无码精品午夜|
久久人人爽人人爽人人AV|
久久天天躁狠狠躁夜夜2020老熟妇|
亚洲中文精品久久久久久不卡|
99久久婷婷国产综合精品草原|
久久午夜无码鲁丝片秋霞|
久久精品18|
国产精品青草久久久久婷婷|
一极黄色视频久久网站|
久久香蕉国产线看观看99|
欧美黑人又粗又大久久久|
色8激情欧美成人久久综合电|
国产亚洲欧美成人久久片|
7777精品久久久大香线蕉|
久久青青草原精品国产软件|
国产成人精品免费久久久久|
久久狠狠爱亚洲综合影院|
欧美日韩精品久久久久
|
国产午夜福利精品久久|
无码任你躁久久久久久老妇App|
精品国产91久久久久久久a|
欧美喷潮久久久XXXXx|
午夜精品久久久久久久久|
免费精品久久天干天干|
亚洲人AV永久一区二区三区久久|
久久国产乱子伦精品免费午夜|
岛国搬运www久久|
久久狠狠一本精品综合网|
久久久久无码精品|
亚洲国产精品无码久久青草|
亚洲成av人片不卡无码久久|
亚洲午夜久久久|