• <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 閱讀(613) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产aⅴ激情无码久久|
av无码久久久久不卡免费网站|
国产精品久久久99|
精品久久国产一区二区三区香蕉|
人妻系列无码专区久久五月天|
99久久国产综合精品女同图片
|
亚洲精品无码久久久久AV麻豆|
日本精品久久久久久久久免费|
一本久久知道综合久久|
久久精品国产亚洲欧美|
久久亚洲电影|
免费精品99久久国产综合精品|
少妇被又大又粗又爽毛片久久黑人|
午夜人妻久久久久久久久|
99久久精品久久久久久清纯|
久久久久亚洲av综合波多野结衣|
久久国产精品久久|
精品久久久无码人妻中文字幕|
国产L精品国产亚洲区久久|
狠狠综合久久综合88亚洲|
美女久久久久久|
777久久精品一区二区三区无码|
久久亚洲AV成人出白浆无码国产|
久久99国产一区二区三区|
国产精品久久久久天天影视|
国产精品久久久久久久app|
亚洲精品高清国产一久久|
久久精品国产网红主播|
久久精品aⅴ无码中文字字幕不卡|
99精品久久久久久久婷婷|
国产精品久久久久久吹潮|
色婷婷综合久久久中文字幕|
亚洲AV伊人久久青青草原|
亚洲国产精品久久久久婷婷老年
|
久久国产成人午夜aⅴ影院|
国内精品久久久久影院优|
久久精品人人槡人妻人人玩AV|
亚洲精品无码久久久久久|
狠狠色噜噜色狠狠狠综合久久|
无码任你躁久久久久久老妇App|
国产精品午夜久久|