• <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啪|
久久综合狠狠综合久久|
99久久亚洲综合精品网站|
国产精品成人99久久久久|
久久免费国产精品|
久久婷婷色综合一区二区|
久久夜色撩人精品国产小说|
99久久国产宗和精品1上映|
国产精品美女久久久久久2018|
精品无码久久久久久久动漫|
久久天天躁狠狠躁夜夜avapp
|
久久九九兔免费精品6|
99999久久久久久亚洲|
久久久久亚洲AV无码专区首JN
|
久久久久亚洲精品天堂久久久久久|
区亚洲欧美一级久久精品亚洲精品成人网久久久久
|
av色综合久久天堂av色综合在|
亚洲一区二区三区日本久久九|
久久精品国产久精国产果冻传媒
|
无码精品久久久天天影视|
激情五月综合综合久久69|
人妻无码久久一区二区三区免费|
久久久国产精华液|
韩国三级中文字幕hd久久精品|
亚洲欧美成人综合久久久|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
偷偷做久久久久网站|
精品国产青草久久久久福利|
99久久无色码中文字幕|
久久久久亚洲av无码专区导航
|
久久夜色精品国产噜噜亚洲a|
91亚洲国产成人久久精品|
国内精品久久久久久99|
无码日韩人妻精品久久蜜桃|
国产成人无码精品久久久性色|
婷婷久久综合九色综合绿巨人
|
好久久免费视频高清|
久久国产精品无码HDAV|
国产一级持黄大片99久久|
精品久久久久久无码专区|
久久99热狠狠色精品一区|