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

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 閱讀(641) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM 、AlgorithmDataStructure課內(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>
            久久精品国产久精国产一老狼| 欧美精品高清视频| 欧美高清hd18日本| 国产精品成人免费| 狠狠色噜噜狠狠狠狠色吗综合| 亚洲国产成人久久综合一区| 亚洲麻豆视频| 久久精品国产999大香线蕉| 快播亚洲色图| 一本色道久久综合狠狠躁的推荐| 性欧美8khd高清极品| 欧美a级片网站| 国产日韩欧美亚洲一区| 亚洲久久在线| 老司机成人在线视频| 99国产精品| 久久综合色播五月| 国产精品爽爽爽| 91久久久久久国产精品| 欧美一区二区精美| 亚洲三级影片| 久久久久国色av免费观看性色| 欧美亚韩一区| 亚洲激情影视| 久久精品中文字幕免费mv| 亚洲国产精品久久久久秋霞影院| 亚洲欧美一区二区激情| 欧美精品123区| 激情综合在线| 翔田千里一区二区| 亚洲美洲欧洲综合国产一区| 久久久久91| 一本色道久久综合亚洲精品按摩 | 亚洲综合电影| 欧美国产亚洲精品久久久8v| 午夜精品久久| 欧美性理论片在线观看片免费| 亚洲人成在线播放网站岛国| 久久精品官网| 亚洲在线一区二区三区| 欧美日本不卡高清| 最新中文字幕亚洲| 久久久久欧美精品| 午夜日韩在线观看| 欧美性大战久久久久久久| 亚洲免费观看| 欧美国产精品人人做人人爱| 久久久久久久久蜜桃| 国产九九视频一区二区三区| 亚洲一区日韩在线| 亚洲区中文字幕| 欧美第一黄色网| 欧美午夜一区| 一本久久综合| 亚洲黄色在线观看| 欧美va天堂在线| 亚洲二区视频在线| 美女图片一区二区| 亚洲精品一二| 欧美精品videossex性护士| 亚洲第一黄色| 欧美成人xxx| 久久婷婷国产综合精品青草| 激情91久久| 麻豆国产va免费精品高清在线| 久久国产66| 在线观看的日韩av| 欧美成人小视频| 玖玖国产精品视频| 亚洲国产视频a| 亚洲第一免费播放区| 免费成人在线视频网站| 91久久夜色精品国产九色| 欧美激情久久久久久| 欧美激情一区二区三区在线视频| 亚洲日本成人| 亚洲日本一区二区| 欧美午夜精品久久久久久超碰| 亚洲午夜激情网页| 亚洲欧美日韩精品久久久| 国产精品一区二区久久久| 亚洲国产高清视频| 亚洲国产成人一区| 欧美成人在线免费观看| 亚洲麻豆av| 洋洋av久久久久久久一区| 欧美视频免费| 性欧美暴力猛交69hd| 欧美一级理论性理论a| 精品不卡一区| 亚洲国产高清在线观看视频| 欧美激情精品久久久久| 亚洲在线观看视频网站| 亚洲一二三级电影| 狠狠狠色丁香婷婷综合久久五月| 欧美风情在线观看| 欧美激情在线免费观看| 亚洲免费视频成人| 久久久久久网| 一个人看的www久久| 亚洲综合视频一区| 在线不卡亚洲| 日韩亚洲一区二区| 国产日韩欧美三级| 亚洲电影第1页| 国产精品成人一区二区| 久久久噜久噜久久综合| 欧美国产亚洲精品久久久8v| 午夜视频一区在线观看| 久久久久国产精品人| 一区二区三区不卡视频在线观看| 亚洲伊人一本大道中文字幕| 亚洲高清免费在线| 99精品国产福利在线观看免费| 国产色产综合色产在线视频| 欧美激情亚洲自拍| 欧美性色综合| 欧美大片在线观看一区| 欧美色区777第一页| 久久五月激情| 香蕉精品999视频一区二区| 亚洲国产免费看| 亚洲午夜精品| 亚洲人成人一区二区在线观看| 亚洲一级黄色av| 亚洲国产欧美久久| 亚洲女人天堂av| 亚洲人成毛片在线播放女女| 亚洲欧美综合精品久久成人| 亚洲国产专区| 欧美亚洲一区二区在线观看| 99国产精品私拍| 欧美中文在线免费| 亚洲视频大全| 久久在线免费视频| 欧美在线高清| 欧美日韩国产精品自在自线| 麻豆久久久9性大片| 国产精品va在线播放| 欧美国产亚洲另类动漫| 国产一区二区精品久久99| 99精品国产福利在线观看免费 | 久久蜜臀精品av| 欧美手机在线| 亚洲国产精品一区二区第四页av| 国产一区二区久久| 亚洲一区二区三区免费在线观看| 亚洲精品日韩欧美| 久久久久国产一区二区三区| 欧美一区91| 欧美系列精品| 亚洲精品少妇网址| 亚洲黄色一区| 久久黄色网页| 欧美影院成人| 国产精品美女| 99精品免费| 一本综合久久| 欧美激情一区二区| 亚洲国产欧美另类丝袜| 亚洲国产经典视频| 老色鬼精品视频在线观看播放| 久久精品国产综合| 国产欧美精品日韩区二区麻豆天美 | 国产欧美日韩精品一区| 亚洲午夜电影网| 亚洲欧美日韩视频一区| 欧美视频二区36p| 一本久久综合亚洲鲁鲁| 夜久久久久久| 欧美日韩一区二区三区高清| 亚洲经典在线看| 日韩视频不卡中文| 欧美精品在线播放| 亚洲激精日韩激精欧美精品| 亚洲国产天堂久久综合| 久久久国产一区二区三区| 久久综合一区| 在线观看视频欧美| 久久亚洲综合网| 欧美国产日韩精品| 亚洲三级电影在线观看| 欧美xart系列高清| 亚洲精品乱码久久久久久久久 | 亚洲深夜激情| 亚洲欧美日韩国产一区| 国产精品欧美日韩| 亚洲欧美日韩直播| 久久久久久精| 在线日本成人| 欧美成人dvd在线视频| 亚洲人成网站在线播| 亚洲图片激情小说| 国产精品一级| 久久不射网站| 欧美成人午夜激情| 亚洲精品男同| 欧美午夜激情视频| 性一交一乱一区二区洋洋av| 久久综合国产精品|