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 阅读(600) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、DataStructure 、课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理