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

coreBugZJ

此 blog 已棄。

EOJ 2525 Light Switching

  1/*
  2EOJ 2525 Light Switching
  3
  4
  5----問(wèn)題描述:
  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 閱讀(645) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmDataStructure課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲三级免费观看| 亚洲视频欧美视频| 巨乳诱惑日韩免费av| 国一区二区在线观看| 久久在线视频在线| 久久欧美中文字幕| 亚洲精品欧美在线| 99精品视频免费在线观看| 国产精品久久福利| 久久se精品一区精品二区| 久久九九久精品国产免费直播 | 亚洲免费婷婷| 国产午夜精品美女视频明星a级 | 欧美主播一区二区三区美女 久久精品人| 亚洲区一区二| 欧美三级日本三级少妇99| 午夜一级久久| 久久精品国产欧美亚洲人人爽| 在线观看亚洲a| 亚洲国产午夜| 国产精品劲爆视频| 久久久水蜜桃av免费网站| 欧美成人tv| 欧美一区二区免费观在线| 久久久久久久精| 99精品福利视频| 午夜精品一区二区三区四区| 亚洲国产人成综合网站| 99热免费精品| 在线日韩欧美视频| 一级成人国产| 亚洲国产精品va在线观看黑人| 日韩视频在线观看免费| 好看的日韩视频| 日韩亚洲国产欧美| 好看的亚洲午夜视频在线| 亚洲精品一区二区三区不| 国产精品一区免费视频| 亚洲激情第一区| 国产一区二区中文字幕免费看| 亚洲精品免费网站| 激情亚洲网站| 欧美亚洲一区| 亚洲午夜精品一区二区三区他趣| 久久久久88色偷偷免费| 亚洲免费在线电影| 欧美777四色影视在线| 久久精品免费播放| 欧美日韩伦理在线| 亚洲电影在线看| 韩国av一区| 午夜精品成人在线| 亚洲自拍高清| 欧美二区在线观看| 欧美xxxx在线观看| 国产一区二区欧美日韩| 亚洲一区二区三区在线视频| 在线性视频日韩欧美| 欧美激情自拍| 亚洲国产va精品久久久不卡综合| 激情视频一区二区| 欧美亚洲一区| 久久精品在线| 国产一在线精品一区在线观看| 一本一本大道香蕉久在线精品| 亚洲免费大片| 欧美日韩国产综合视频在线| 亚洲国产日韩欧美在线99 | 欧美日韩在线观看视频| 91久久精品一区| 日韩亚洲在线| 欧美日韩一区二区三区在线视频| 亚洲伦伦在线| 亚洲一级网站| 国产精品夜夜夜| 性久久久久久久久| 久久综合九九| 亚洲国产欧美不卡在线观看| 女仆av观看一区| 99re热这里只有精品免费视频| 一区二区三区 在线观看视| 欧美伦理a级免费电影| 日韩亚洲在线观看| 午夜在线电影亚洲一区| 国产日本欧美一区二区| 久久激情五月激情| 欧美激情在线观看| 亚洲一区二区在线视频| 国产精品外国| 久久国产色av| 亚洲人体影院| 翔田千里一区二区| 在线观看视频亚洲| 欧美日韩a区| 羞羞色国产精品| 欧美电影免费观看| 一个人看的www久久| 国产精品色网| 久久在线精品| 亚洲午夜精品一区二区| 久久久久国产精品一区| 亚洲区欧美区| 国产偷自视频区视频一区二区| 久久这里只有| 亚洲一区国产| 亚洲国产精品高清久久久| 亚洲一区欧美激情| 玉米视频成人免费看| 欧美劲爆第一页| 欧美自拍偷拍| 一本色道久久加勒比88综合| 久久深夜福利免费观看| av成人国产| 一区国产精品| 国产美女精品视频| 欧美69wwwcom| 欧美在线播放一区| 亚洲狼人综合| 亚洲国产精品www| 久久久www免费人成黑人精品| 一本高清dvd不卡在线观看| 国产一区在线视频| 国产精品久久久久aaaa樱花| 欧美www在线| 欧美一区二区三区男人的天堂| 99精品久久久| 亚洲精品日本| 亚洲激情电影在线| 免费在线看一区| 久久久久久久久久久久久女国产乱| 中文网丁香综合网| 日韩天堂在线视频| 亚洲黄色有码视频| 激情综合五月天| 国产综合色精品一区二区三区| 国产精品久久久久一区二区三区共| 免费看的黄色欧美网站| 久久久亚洲一区| 性色av一区二区三区在线观看| 这里只有精品视频在线| 日韩视频一区二区在线观看| 亚洲第一视频网站| 欧美成人午夜| 欧美激情自拍| 亚洲国产乱码最新视频| 亚洲国产成人久久| 亚洲国产午夜| 99精品视频免费观看| 亚洲毛片一区| 在线亚洲激情| 亚洲一区二区三区在线看| 亚洲图片在线观看| 午夜精品视频在线| 亚洲欧美在线免费| 欧美一区二区在线视频| 欧美一级黄色录像| 久久久青草婷婷精品综合日韩| 欧美在线一二三| 麻豆精品在线视频| 欧美国产激情| 国产精品久久久久久久久久ktv | 麻豆精品网站| 欧美片在线观看| 国产精品成人在线| 国内精品亚洲| 亚洲乱码精品一二三四区日韩在线 | 午夜精品一区二区三区在线| 欧美一区二区三区电影在线观看| 久久国产精品久久久久久久久久| 麻豆精品传媒视频| 欧美精品久久一区二区| 国产精品黄色| 在线观看日韩www视频免费| 亚洲精品久久久久久下一站| 夜夜爽av福利精品导航| 午夜精品亚洲一区二区三区嫩草| 久久综合色天天久久综合图片| 亚洲国产精品va| 亚洲网站视频| 免费永久网站黄欧美| 国产精品久久国产精麻豆99网站| 国产日韩一区二区三区| 亚洲人体大胆视频| 欧美在线日韩| 亚洲第一视频网站| 亚洲欧美电影院| 欧美h视频在线| 国产日韩欧美黄色| 99精品欧美一区二区三区综合在线 | 国产欧美va欧美不卡在线| 亚洲高清久久| 欧美一级淫片aaaaaaa视频| 欧美ed2k| 午夜日本精品| 欧美日韩亚洲网| 亚洲国产91色在线| 久久99在线观看| 一区二区av在线| 欧美成人免费在线| 激情一区二区三区|