• <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 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 2525 Light Switching
		
            
		
              1/*
              2EOJ 2525 Light Switching
              3
              4
              5----問題描述：
              6
              7Farmer John tries to keep the cows sharp by letting them play with intellectual toys.
              8One of the larger toys is the lights in the barn.
              9
             10Each of the N (2 <= N <= 100,000) cow stalls conveniently numbered 1..N has a colorful light above it.
             11
             12At the beginning of the evening, all the lights are off. The cows control the lights with a set of N pushbutton switches that toggle the lights; pushing switch i changes the state of light i from off to on or from on to off.
             13
             14The cows read and execute a list of M (1 <= M <= 100,000) operations expressed as one of two integers (0 <= operation <= 1).
             15
             16The first operation (denoted by a 0 command) includes two subsequent integers S_i and E_i (1 <= S_i <= E_i <= N) that indicate a starting switch and ending switch. They execute the operation by pushing each pushbutton from S_i through E_i inclusive exactly once.
             17
             18The second operation (denoted by a 1 command) asks the cows to count how many lights are on in the range given by two integers S_i and E_i (1 <= S_i <= E_i <= N) which specify the inclusive range in which the cows should count the number of lights that are on.
             19
             20Help FJ ensure the cows are getting the correct answer by processing the list and producing the proper counts. 
             21
             22
             23----輸入：
             24
             25* Line 1: Two space-separated integers: N and M
             26
             27* Lines 2..M+1: Each line represents an operation with three space-separated integers: operation, S_i, and E_i 
             28
             29
             30----輸出：
             31
             32* Lines 1..number of queries: For each output query, print the count as an integer by itself on a single line.
             33
             34
             35----樣例輸入：
             36
             374 5
             380 1 2
             390 2 4
             401 2 3
             410 2 4
             421 1 4
             43
             44INPUT DETAILS:
             45 
             46Four lights; five commands. Here is the sequence that should be processed:
             47
             48=========Lights
             49=========1 2 3 4
             50Init:====O O O O , O = off * = on
             510 1 2 -->* * O O ,toggle lights 1 and 2
             520 2 4 -->* O * *
             531 2 3 -->1 ,count the number of lit lights in range 2..3
             540 2 4 -->* * O O ,toggle lights 2, 3, and 4
             551 1 4 -->2 ,count the number of lit lights in the range 1..4
             56
             57
             58----樣例輸出：
             59
             601
             612
             62
             63
             64----分析：
             65
             66
             67*/
             68
             69
             70template<unsigned int N>
             71class CProblem
             72{
             73public : 
             74        void init( int b, int e ){
             75                init( 1, b, e );
             76        }
             77        int query( int b, int e ){
             78                begin = b;
             79                end   = e;
             80                return query( 1 );
             81        }
             82        void modify( int b, int e ){
             83                begin = b;
             84                end   = e;
             85                modify( 1 );
             86        }
             87
             88private : 
             89        void init( int node, int b, int e ){
             90                left    [ node ] = b;
             91                right   [ node ] = e;
             92                sum     [ node ] = 0;
             93                modified[ node ] = false;
             94                if( b + 1 < e ){
             95                        init( node + node, b, ( b + e ) / 2 );
             96                        init( node + node + 1, ( b + e ) / 2, e );
             97                }
             98        }
             99        int query( int node ){
            100                if( ( end <= left[ node ] ) || ( right[ node ] <= begin ) ){
            101                        return 0;
            102                }
            103                if( ( begin <= left[ node ] ) && ( right[ node ] <= end ) ){
            104                        return sum[ node ];
            105                }
            106                int len = ( right[ node ] > end ? end : right[ node ] ) - ( left[ node ] < begin ? begin : left[ node ] );
            107                return ( modified[ node ] ) ? ( len - query( node + node ) - query( node + node + 1 ) ) : ( query( node + node ) + query( node + node + 1 ) );
            108        }
            109        void modify( int node ){
            110                if( ( end <= left[ node ] ) || ( right[ node ] <= begin ) ){
            111                        return;
            112                }
            113                if( ( begin <= left[ node ] ) && ( right[ node ] <= end ) ){
            114                        sum[ node ] = right[ node ] - left[ node ] - sum[ node ];
            115                        modified[ node ] = ! modified[ node ];
            116                        return;
            117                }
            118                modify( node + node );
            119                modify( node + node + 1 );
            120                sum[ node ] = ( modified[ node ] ) ? ( right[ node ] - left[ node ] - sum[ node + node ] - sum[ node + node + 1 ] ) : ( sum[ node + node ] + sum[ node + node + 1 ] );
            121        }
            122
            123        int  left[ N + N ], right[ N + N ], sum[ N + N ], begin, end;
            124        bool modified[ N + N ];
            125}            ;
            126
            127#include <iostream>
            128#include <cstdio>
            129
            130using namespace std;
            131
            132CProblem<150003> prob;
            133
            134int main(){
            135        int n, m, cmd, a, b;
            136        scanf( "%d%d", &n, &m );
            137        prob.init( 1, n + 1 );
            138        while( m-- ){
            139                scanf( "%d%d%d", &cmd, &a, &b );
            140                if( cmd ){
            141                        printf( "%d\n", prob.query( a, b + 1 ) );
            142                }
            143                else{
            144                        prob.modify( a, b + 1 );
            145                }
            146        }
            147        return 0;
            148}
            149
            
		
            
			posted on 2012-04-22 22:46 coreBugZJ 閱讀(619) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产伊人久久|
久久99热精品|
久久夜色精品国产噜噜麻豆|
思思久久好好热精品国产|
久久中文字幕人妻熟av女|
久久精品人人做人人爽97|
精品熟女少妇aⅴ免费久久|
精品久久久久久中文字幕大豆网|
久久w5ww成w人免费|
一本久久a久久精品综合香蕉|
中文字幕无码免费久久|
狠狠久久综合伊人不卡|
亚洲人成网亚洲欧洲无码久久|
久久精品国产亚洲AV无码麻豆|
久久亚洲精品成人AV|
欧美成a人片免费看久久|
久久婷婷五月综合色奶水99啪|
久久福利片|
国产精品伊人久久伊人电影|
午夜精品久久久久久99热|
日韩十八禁一区二区久久|
国产福利电影一区二区三区久久老子无码午夜伦不|
欧美久久一区二区三区|
国产激情久久久久影院|
久久国产高清字幕中文|
欧洲成人午夜精品无码区久久
|
国内精品久久人妻互换|
久久亚洲国产最新网站|
久久久久久国产a免费观看不卡|
久久久91精品国产一区二区三区|
97精品伊人久久久大香线蕉|
一级a性色生活片久久无|
青青热久久国产久精品|
手机看片久久高清国产日韩|
久久精品中文字幕有码|
久久婷婷五月综合97色直播|
久久精品国产精品亚洲|
久久婷婷五月综合97色直播|
久久夜色撩人精品国产|
亚洲欧洲久久av|
老男人久久青草av高清|