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

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            一本久久知道综合久久| 亚洲精品日韩久久| 欧美性猛交xxxx乱大交蜜桃| 另类亚洲自拍| 国产精品美女主播| 亚洲精品韩国| 好吊色欧美一区二区三区四区| 一本色道88久久加勒比精品 | 久久精品国产免费看久久精品| 欧美华人在线视频| 男男成人高潮片免费网站| 国产日韩精品入口| 亚洲一区制服诱惑| 亚洲男人影院| 欧美日韩一区二区在线观看视频| 欧美大片在线看| 精品69视频一区二区三区| 校园春色国产精品| 久久av一区二区| 国产女优一区| 亚洲欧美日本精品| 欧美亚洲综合在线| 国产精品影音先锋| 在线综合欧美| 午夜久久资源| 国产午夜精品全部视频播放 | 看欧美日韩国产| 老司机免费视频一区二区| 狠狠色丁香久久婷婷综合_中| 亚洲欧美三级伦理| 欧美一区二粉嫩精品国产一线天| 国产精品视频精品| 校园春色国产精品| 久久精品免费播放| 亚洲电影网站| 欧美国产日韩一区二区在线观看 | 欧美日韩视频在线观看一区二区三区 | 欧美一二三区精品| 久久久久国产精品麻豆ai换脸| 国产一区二区三区在线免费观看 | 久久国产视频网| 噜噜噜久久亚洲精品国产品小说| 国产在线精品成人一区二区三区 | 亚洲一区二区三区视频播放| 欧美日韩亚洲高清| 这里只有精品电影| 欧美一区二区三区四区在线观看地址| 国产欧美日韩高清| 久久久久国内| 亚洲精品日韩激情在线电影| 亚洲一区二区三区中文字幕在线| 国产精品外国| 久久看片网站| 9人人澡人人爽人人精品| 欧美一区二区三区四区视频| 狠狠综合久久av一区二区老牛| 久久综合网色—综合色88| 亚洲精品久久久久久久久| 午夜视频一区| 亚洲精品1区2区| 欧美亚一区二区| 久久久久久综合网天天| 亚洲黄色视屏| 欧美一区日本一区韩国一区| 亚洲第一色中文字幕| 欧美日韩免费一区| 久久不见久久见免费视频1| 亚洲国产精品免费| 欧美一区激情| 亚洲免费成人av电影| 国产欧美日韩不卡免费| 免费不卡亚洲欧美| 亚洲欧美日韩精品久久| 亚洲第一精品夜夜躁人人躁| 欧美一级视频精品观看| 亚洲黄色成人| 国产夜色精品一区二区av| 欧美日韩国产精品一区二区亚洲 | 欧美午夜精品久久久久久孕妇 | 久久人人精品| 亚洲欧美国产精品va在线观看| 在线观看视频免费一区二区三区| 国产精品久久福利| 欧美大色视频| 久久久精品国产免费观看同学| 一本久道久久综合狠狠爱| 蜜臀久久99精品久久久画质超高清| 亚洲综合大片69999| 亚洲精一区二区三区| 国内外成人免费激情在线视频| 欧美日韩国产专区| 嫩草影视亚洲| 久久综合一区二区三区| 欧美一区二区三区免费在线看| 一区二区三区你懂的| 欧美激情视频一区二区三区免费 | 久久久久国产精品www| 亚洲影视九九影院在线观看| 亚洲免费电影在线| 亚洲国产合集| 久久久精品国产免大香伊| 欧美亚洲一区二区在线观看| 亚洲一级高清| 中文久久乱码一区二区| 亚洲最黄网站| 99国产精品| 99国产精品久久| 亚洲精品欧美一区二区三区| 亚洲国产一区二区三区青草影视| 精品动漫一区二区| 国产一区清纯| 国产一区二区三区黄| 国产日韩欧美一区| 国产日韩欧美另类| 国产专区一区| 极品裸体白嫩激情啪啪国产精品| 国产日本欧美一区二区三区| 国产日韩视频| 国模精品一区二区三区色天香| 国产一区二区日韩| 激情91久久| 亚洲片在线观看| 一区二区三区日韩| 亚洲永久精品国产| 欧美在线网站| 免费在线观看精品| 亚洲人成人一区二区三区| 99精品欧美| 午夜精品亚洲| 老司机67194精品线观看| 欧美高清视频一二三区| 国产精品videossex久久发布| 国产精品一区久久| 尤物在线精品| 一区二区三区av| 久久国产精品黑丝| 欧美成人国产| 在线视频欧美日韩| 欧美一级在线亚洲天堂| 美女精品网站| 国产精品精品视频| 激情综合激情| 亚洲少妇在线| 久久免费黄色| 日韩午夜一区| 欧美专区亚洲专区| 欧美日本高清视频| 国产在线高清精品| 一本色道久久综合亚洲精品不| 羞羞答答国产精品www一本| 麻豆成人av| 国产精品99久久久久久久久久久久 | 一个人看的www久久| 欧美一区二区三区啪啪| 亚洲电影第三页| 亚洲欧美日韩国产中文| 欧美成人在线影院| 国产日韩精品一区二区三区在线| 亚洲欧洲午夜| 久久国产精品久久久| 亚洲人成精品久久久久| 久久久久久一区二区三区| 国产精品免费电影| 日韩午夜在线播放| 牛人盗摄一区二区三区视频| 亚洲一区二区三区视频| 欧美久久九九| 亚洲国产高潮在线观看| 久久国产欧美| 亚洲天堂男人| 欧美日韩免费观看中文| 亚洲国产精品久久久久秋霞蜜臀| 久久国产精品99国产精| 一二三四社区欧美黄| 欧美激情性爽国产精品17p| 亚洲高清免费视频| 久久网站免费| 欧美伊人久久久久久久久影院 | 欧美一区二区视频在线| 日韩网站在线观看| 久久综合精品一区| 狠狠入ady亚洲精品经典电影| 久久av一区二区三区| 国产精品99久久久久久有的能看| 欧美日本亚洲| 一本一道久久综合狠狠老精东影业 | 麻豆国产精品一区二区三区| 亚洲欧美影院| 国产精品一区二区在线观看| 亚洲主播在线播放| 一区二区三区www| 欧美日精品一区视频| 宅男精品视频| 一本色道久久综合亚洲精品按摩| 欧美精品久久久久a| 99re66热这里只有精品4| 亚洲黄色免费网站| 欧美黄色aaaa| 一区二区精品| 正在播放亚洲|