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





            
	    
    




            






            

				

            


    
    







            
	   
	



久久电影网一区|
亚洲AV日韩AV永久无码久久|
无码任你躁久久久久久|
18岁日韩内射颜射午夜久久成人|
亚洲精品乱码久久久久久蜜桃|
欧美日韩精品久久久久|
99久久婷婷国产综合亚洲|
久久无码中文字幕东京热|
人人狠狠综合久久88成人|
色诱久久av|
亚洲国产精品无码久久青草|
国产精品99久久精品爆乳|
亚洲狠狠婷婷综合久久蜜芽|
日本WV一本一道久久香蕉|
国产叼嘿久久精品久久|
色噜噜狠狠先锋影音久久|
97久久香蕉国产线看观看|
A狠狠久久蜜臀婷色中文网|
久久婷婷五月综合97色一本一本|
亚洲香蕉网久久综合影视|
久久国产欧美日韩精品|
欧洲精品久久久av无码电影|
久久久久久亚洲精品成人|
久久精品国产精品亚洲精品|
国产农村妇女毛片精品久久|
开心久久婷婷综合中文字幕|
久久强奷乱码老熟女|
亚洲国产精品无码久久|
久久福利片|
99久久国产热无码精品免费
|
色欲综合久久躁天天躁|
久久婷婷五月综合97色直播|
蜜臀av性久久久久蜜臀aⅴ麻豆|
久久久久久亚洲AV无码专区|
久久国产精品一区|
久久综合狠狠色综合伊人|
久久婷婷国产综合精品|
伊人久久大香线蕉av不变影院|
精品久久久久久亚洲精品|
久久久久99这里有精品10|
国产AV影片久久久久久|