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

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 閱讀(633) 評論(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>
            日韩视频亚洲视频| 国产精品99久久久久久久女警 | 欧美国产精品一区| 亚洲精品激情| 在线中文字幕日韩| 国产精品久久久久免费a∨| 欧美一区=区| 久久精品国产欧美激情 | 欧美成人资源| 亚洲无线视频| 久久精品国产77777蜜臀| 亚洲第一网站| 99视频一区二区| 国产日韩欧美在线视频观看| 麻豆av一区二区三区| 欧美精品一区二区高清在线观看| 亚洲一级二级在线| 欧美在线视频播放| 宅男噜噜噜66一区二区66| 亚洲欧美高清| 亚洲伦理在线免费看| 亚洲男人av电影| 亚洲欧洲日韩在线| 亚洲欧美在线视频观看| 亚洲精品乱码久久久久久日本蜜臀 | 亚洲国产高清自拍| 国产精品久久网站| 欧美激情一区二区三区| 国产精品一区二区久久国产| 亚洲高清视频的网址| 国产欧美69| 日韩亚洲综合在线| 在线精品视频一区二区三四| 亚洲一区二区三区色| 亚洲精品欧美日韩专区| 久久九九热re6这里有精品 | 在线日本成人| 亚洲一区二区少妇| 亚洲精品免费网站| 久久精品国产亚洲aⅴ| 亚洲综合日韩中文字幕v在线| 久久亚洲精选| 裸体女人亚洲精品一区| 国产欧美一区二区三区沐欲| 亚洲精品一区二区在线| 亚洲福利专区| 久久综合伊人77777| 久久久久久网站| 国产小视频国产精品| 亚洲一二三区在线观看| 亚洲视频一二| 欧美日韩免费一区二区三区视频| 免费欧美在线| 亚洲电影免费观看高清完整版| 久久成人av少妇免费| 欧美资源在线| 国产午夜精品全部视频播放| 亚洲欧美精品在线观看| 性刺激综合网| 国产精品男gay被猛男狂揉视频| 国产精品99久久99久久久二8 | 欧美精品日韩精品| 亚洲福利视频二区| 亚洲三级性片| 欧美精品久久天天躁| 亚洲经典在线看| 日韩视频一区二区| 欧美日韩精品一区视频| 洋洋av久久久久久久一区| 亚洲伊人一本大道中文字幕| 国产精品国产亚洲精品看不卡15 | 一片黄亚洲嫩模| 欧美一区二区福利在线| 国产日韩欧美制服另类| 久久成人综合视频| 欧美激情视频一区二区三区免费| 亚洲国产精品一区二区尤物区 | 欧美插天视频在线播放| 亚洲精品少妇30p| 亚洲女同精品视频| 国语自产精品视频在线看| 麻豆av福利av久久av| 亚洲精品美女在线观看| 欧美亚洲一区二区在线| 国产在线观看一区| 欧美成人一区二区| 亚洲一区二区影院| 免费观看成人网| 一区二区欧美在线观看| 国产欧美日韩精品a在线观看| 久久狠狠亚洲综合| 亚洲精品在线一区二区| 久久精品国语| 日韩一级黄色av| 国产日韩欧美在线视频观看| 欧美v国产在线一区二区三区| 亚洲精品自在在线观看| 久久久久网址| 中日韩高清电影网| 亚洲大片av| 国产精品嫩草99av在线| 欧美暴力喷水在线| 午夜精品久久久久久久久久久久| 欧美成人综合在线| 香蕉久久夜色精品| 亚洲欧洲一区二区在线播放| 国产精品欧美日韩久久| 免费在线国产精品| 午夜电影亚洲| 一区二区三区成人精品| 欧美激情视频网站| 久久精品国内一区二区三区| 在线综合视频| 91久久夜色精品国产网站| 国产欧美日韩在线| 欧美午夜大胆人体| 欧美寡妇偷汉性猛交| 久久久另类综合| 性欧美大战久久久久久久免费观看| 亚洲精品视频一区| 欧美波霸影院| 噜噜噜91成人网| 欧美资源在线观看| 欧美诱惑福利视频| 午夜精品久久久久久久| 99这里有精品| 亚洲伦理在线观看| 亚洲日本黄色| 亚洲欧洲视频| 亚洲人成网站在线播| 在线观看精品| 亚洲国产成人不卡| 亚洲国产成人av好男人在线观看| 国产一区二区三区在线观看网站| 国产精品普通话对白| 国产精品亚洲成人| 国产精品亚洲一区二区三区在线| 欧美系列精品| 国产精品女主播在线观看| 国产精品成人免费| 国产精品久久久久久影视| 国产精品国产成人国产三级| 欧美视频二区| 国产精品免费久久久久久| 国产精品国产精品| 国产精品视频xxxx| 国产毛片一区二区| 国产亚洲在线| 亚洲美女av在线播放| 亚洲精品免费一二三区| 日韩视频在线免费观看| 宅男精品视频| 欧美亚洲一区三区| 久久色中文字幕| 欧美国内亚洲| 国产精品入口麻豆原神| 国产亚洲福利| 亚洲经典视频在线观看| 日韩网站在线| 亚洲欧美日韩精品久久亚洲区 | 欧美成人xxx| 亚洲欧洲一区二区在线观看| 一区二区av在线| 欧美一区2区视频在线观看| 老鸭窝毛片一区二区三区| 欧美激情精品久久久久久蜜臀 | 91久久香蕉国产日韩欧美9色| 9l视频自拍蝌蚪9l视频成人| 午夜欧美大尺度福利影院在线看| 久久www成人_看片免费不卡| 欧美成人黑人xx视频免费观看| 亚洲片区在线| 久久精品国产999大香线蕉| 嫩草影视亚洲| 国产日韩欧美综合| 日韩一级片网址| 久久久久久久久久久久久久一区| 欧美成人免费全部观看天天性色| 一本久久综合亚洲鲁鲁五月天| 久久精品国产第一区二区三区最新章节 | 欧美一级播放| 欧美激情亚洲自拍| 亚洲欧美精品在线观看| 欧美成人网在线| 黄色精品在线看| 亚洲综合精品一区二区| 欧美成人一区二区三区片免费| 国产精品99久久久久久有的能看 | 久久精品免视看| 欧美午夜精品理论片a级按摩| 极品裸体白嫩激情啪啪国产精品| 亚洲一区二区三区国产| 欧美激情中文字幕一区二区| 性久久久久久久久久久久| 欧美日韩亚洲综合| 亚洲免费高清| 欧美国产成人精品| 久久蜜桃香蕉精品一区二区三区| 国产精品综合色区在线观看| 一区二区三区精密机械公司|