• <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) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、DataStructure 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



伊人久久大香线蕉综合网站|
亚洲欧美国产精品专区久久|
大香伊人久久精品一区二区|
久久天堂电影网|
国内精品伊人久久久久av一坑|
亚洲欧美日韩久久精品第一区|
性做久久久久久久久|
亚洲欧美日韩精品久久亚洲区
|
精品熟女少妇a∨免费久久|
久久久久亚洲AV片无码下载蜜桃|
成人午夜精品无码区久久|
久久婷婷五月综合色奶水99啪|
婷婷久久久亚洲欧洲日产国码AV|
人妻精品久久久久中文字幕一冢本
|
中文精品久久久久人妻不卡|
久久人人爽人人爽人人片AV麻烦|
狠狠色综合久久久久尤物|
久久久久九国产精品|
国色天香久久久久久久小说|
狠狠色婷婷久久一区二区三区|
狠狠色丁香久久婷婷综|
色天使久久综合网天天|
久久人人妻人人爽人人爽|
久久久久久久尹人综合网亚洲|
很黄很污的网站久久mimi色
|
欧美日韩中文字幕久久久不卡|
国产免费久久精品99re丫y|
亚洲精品无码久久毛片|
久久综合给合久久国产免费|
久久婷婷综合中文字幕|
久久亚洲精品无码aⅴ大香|
999久久久免费精品国产|
一本久久综合亚洲鲁鲁五月天|
东京热TOKYO综合久久精品|
久久这里只有精品视频99|
久久久久久久久久久久中文字幕
|
久久亚洲中文字幕精品有坂深雪|
精品一区二区久久久久久久网站|
性欧美大战久久久久久久|
国产91久久综合|
久久国产高清字幕中文|