coreBugZJ

此 blog 已棄。

EOJ 2525 Light Switching

/*
2

EOJ 2525 Light Switching
3

----問題描述：
6

Farmer John tries to keep the cows sharp by letting them play with intellectual toys.
8

One of the larger toys is the lights in the barn.
9

Each of the N (2 <= N <= 100,000) cow stalls conveniently numbered 1..N has a colorful light above it.
11

At 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

The cows read and execute a list of M (1 <= M <= 100,000) operations expressed as one of two integers (0 <= operation <= 1).
15

The 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

The 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

Help FJ ensure the cows are getting the correct answer by processing the list and producing the proper counts.
21

----輸入：
24

* Line 1: Two space-separated integers: N and M
26

* Lines 2..M+1: Each line represents an operation with three space-separated integers: operation, S_i, and E_i
28

----輸出：
31

* Lines 1..number of queries: For each output query, print the count as an integer by itself on a single line.
33

----樣例輸入：
36

4 5
38

0 1 2
39

0 2 4
40

1 2 3
41

0 2 4
42

1 1 4
43

INPUT DETAILS:
45

Four lights; five commands. Here is the sequence that should be processed:
47

=========Lights
49

=========1 2 3 4
50

Init:====O O O O , O = off * = on
51

0 1 2 -->* * O O ,toggle lights 1 and 2
52

0 2 4 -->* O * *
53

1 2 3 -->1 ,count the number of lit lights in range 2..3
54

0 2 4 -->* * O O ,toggle lights 2, 3, and 4
55

1 1 4 -->2 ,count the number of lit lights in the range 1..4
56

----樣例輸出：
59

1
61

2
62

----分析：
65

*/
68

template<unsigned int N>
71

class CProblem
72

{
73

public :
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

private :
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

130

using namespace std;
131

132

CProblem<150003> prob;
133

134

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

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 2525 Light Switching