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

coreBugZJ

此 blog 已棄。

POJ 2528 Mayor's posters

  1/*
  2POJ 2528 Mayor's posters
  3
  4
  5----問題描述:
  6
  7The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim.
  8The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules: 
  9Every candidate can place exactly one poster on the wall. 
 10All posters are of the same height equal to the height of the wall;
 11the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
 12The wall is divided into segments and the width of each segment is one byte.
 13Each poster must completely cover a contiguous number of wall segments.
 14
 15They have built a wall 10000000 bytes long (such that there is enough place for all candidates).
 16When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width.
 17Moreover, the candidates started placing their posters on wall segments already occupied by other posters.
 18Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
 19Your task is to find the number of visible posters when all the posters are placed given the information about posters' size,
 20their place and order of placement on the electoral wall.
 21
 22
 23----輸入:
 24
 25The first line of input contains a number c giving the number of cases that follow.
 26The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 , , ri.
 27
 28
 29----輸出:
 30
 31For each input data set print the number of visible posters after all the posters are placed.
 32
 33
 34----樣例輸入:
 35
 361
 375
 381 4
 392 6
 408 10
 413 4
 427 10
 43
 44
 45----樣例輸出:
 46
 474
 48
 49
 50----分析:
 51
 52線段樹。
 53
 54
 55*/

 56
 57
 58
 59#include <iostream>
 60#include <algorithm>
 61
 62using namespace std;
 63
 64template<unsigned int N>
 65class CSegTree
 66{
 67public : 
 68        void init( int b, int e ){
 69                init( 1, b, e );
 70        }

 71        void modify( int b, int e, int d ){
 72                begin = b;
 73                end   = e;
 74                data  = d;
 75                modify( 1 );
 76        }

 77        int query( void ){
 78                memset( visible, 0sizeof( visible ) );
 79                query( 1 );
 80                data = 0;
 81                forint i = 1; i < N; ++i ){
 82                        if( visible[ i ] ){
 83                                ++data;
 84                        }

 85                }

 86                return data;
 87        }

 88
 89private : 
 90        void init( int node, int b, int e ){
 91                left[ node ]  = b;
 92                right[ node ] = e;
 93                id[ node ]    = 0;
 94                if( b < e ){
 95                        init( node << 1, b, ( b + e ) >> 1 );
 96                        init( ( node << 1 ) + 1, ( ( b + e ) >> 1 ) + 1, e );
 97                }

 98        }

 99        void modify( int node ){
100                if( ( end < left[ node ] ) || ( right[ node ] < begin ) ){
101                        return;
102                }

103                if( data == id[ node ] ){
104                        return;
105                }

106                if( ( begin <= left[ node ] ) && ( right[ node ] <= end ) ){
107                        id[ node ] = data;
108                        return;
109                }

110                if( id[ node ] ){
111                        id[ node << 1 ] = id[ ( node << 1 ) + 1 ] = id[ node ];
112                        id[ node ] = 0;
113                }

114                modify( node << 1 );
115                modify( ( node << 1 ) + 1 );
116                if( id[ node << 1 ] == id[ ( node << 1 ) + 1 ] ){
117                        id[ node ] = id[ node << 1 ];
118                }

119        }

120        void query( int node ){
121                if( id[ node ] ){
122                        visible[ id[ node ] ] = true;
123                        return;
124                }

125                if( left[ node ] >= right[ node ] ){
126                        return;
127                }

128                query( node << 1 );
129                query( ( node << 1 ) + 1 );
130        }

131
132        enum{ L = N * 3 };
133        typedef int IA[ L ];
134        IA left, right, id;
135        bool visible[ N ];
136
137        int begin, end, data;
138        
139}
;
140
141template<unsigned int N, unsigned int NT>
142class CLine
143{
144public : 
145        friend istream & operator>>( istream & is, CLine<N,NT> & li ){
146                is >> li.n;
147                forint i = 1; i <= li.n; ++i ){
148                        is >> li.left[ i ] >> li.right[ i ];
149                }

150                return is;
151        }

152        void init_tree( CSegTree<NT> & tree ){
153                int i, j;
154                n2 = n << 1;
155                for( j = i = 1; i <= n; ++i,++j ){
156                        line[ j ].p     = left[ i ];
157                        line[ j ].id    = i;
158                        line[ j ].bLeft = true;
159
160                        ++j;
161                        line[ j ].p     = right[ i ];
162                        line[ j ].id    = i;
163                        line[ j ].bLeft = false;
164                }

165                sort( line + 1, line + n2 + 1 );
166                tp = 0;
167                line[ 0 ].p = -123456;
168                for( i = 1; i <= n2; ++i ){
169                        if( line[ i ].bLeft ){
170                                left[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
171                        }

172                        else{
173                                right[ line[ i ].id ] = ( line[ i - 1 ].p == line[ i ].p ? tp : ++tp );
174                        }

175                }

176                tree.init( 1, tp );
177                for( i = 1; i <= n; ++i ){
178                        tree.modify( left[ i ], right[ i ], i );
179                }

180        }

181
182private : 
183        struct SLine
184        {
185                bool operator<const SLine & b ){
186                        return p < b.p;
187                }

188                int  p, id;
189                bool bLeft;
190        }
;
191        SLine  line[ N * 2 ];
192        int    left[ N ], right[ N ], n, n2, tp;
193}
;
194
195const int L = 30009, TL = L * 2;
196CSegTree<TL> tree;
197CLine<L,TL> line;
198
199int main(){
200        int td;
201        cin >> td;
202        while( td-- ){
203                cin >> line;
204                line.init_tree( tree );
205                cout << tree.query() << endl;
206        }

207        return 0;
208}

209

posted on 2012-04-22 22:50 coreBugZJ 閱讀(557) 評論(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>
            国产精品高潮呻吟视频| 夜夜嗨av一区二区三区网站四季av | 日韩亚洲精品电影| 女同一区二区| 免费观看30秒视频久久| 麻豆国产va免费精品高清在线| 久久亚洲影音av资源网| 老司机凹凸av亚洲导航| 欧美精品一区二区精品网| 欧美欧美天天天天操| 国产精品国产精品国产专区不蜜| 国产精品毛片| 亚洲电影免费观看高清完整版在线观看 | 99精品欧美| 一级日韩一区在线观看| 亚洲欧美成人综合| 久久国产欧美| 欧美日韩国产一区精品一区| 国产精品一二一区| 在线看一区二区| 亚洲一二三区在线观看| 欧美专区在线观看| 欧美激情精品久久久久久蜜臀| 亚洲精品一区在线| 欧美一区二区三区视频在线观看| 美女视频黄 久久| 国产精品国产三级国产普通话99| 国产亚洲精品一区二区| 亚洲国产精品成人久久综合一区| 亚洲日韩成人| 香港久久久电影| 久久久久久夜| 中文在线一区| 可以看av的网站久久看| 国产精品你懂的在线| 久久综合九色99| 国产日韩欧美三区| 最新69国产成人精品视频免费| 亚洲一区国产精品| 欧美高清日韩| 欧美一区不卡| 欧美人妖另类| 黄色亚洲在线| 欧美一区二区日韩一区二区| 亚洲日本va在线观看| 亚洲国产综合在线看不卡| 久久精品九九| 国产欧美日韩综合| 亚洲欧美一级二级三级| 亚洲区一区二区三区| 久久婷婷av| 黄色在线一区| 久久精品免费观看| 亚洲在线观看免费| 欧美视频在线一区| 一区二区三区高清在线观看| 欧美激情一区二区三区在线视频观看| 欧美在线|欧美| 国产日韩成人精品| 久久精品亚洲一区二区| 亚洲一区综合| 欧美精品一区在线发布| 亚洲精品视频在线观看免费| 麻豆精品在线视频| 久久午夜av| 亚洲国产婷婷综合在线精品| 久久综合久久综合九色| 久久久99爱| 亚洲黄色大片| 亚洲国产日韩一级| 麻豆国产精品va在线观看不卡| 狠狠色狠狠色综合日日小说| 久久久精品久久久久| 久久精品官网| 欧美国产1区2区| 一本一道久久综合狠狠老精东影业 | 亚洲国产精品高清久久久| 免费欧美日韩| aⅴ色国产欧美| 在线亚洲免费视频| 欧美午夜国产| 午夜欧美不卡精品aaaaa| 亚洲男女自偷自拍| 韩国av一区二区三区在线观看| 欧美18av| 欧美午夜精品理论片a级大开眼界 欧美午夜精品理论片a级按摩 | 久久久久久久综合色一本| 亚洲免费一在线| 韩国一区电影| 亚洲激情中文1区| 国产精品高潮呻吟久久| 久久亚洲一区二区三区四区| 欧美黄色影院| 欧美在线看片a免费观看| 久久久免费av| 亚洲一区二区在线视频| 久久久久久亚洲精品中文字幕| 亚洲久色影视| 午夜精品久久久久久久99水蜜桃| 在线 亚洲欧美在线综合一区| 亚洲免费福利视频| 国内精品美女av在线播放| 亚洲高清不卡av| 国产农村妇女精品| 亚洲黄色免费网站| 国产日韩欧美在线| 亚洲精品中文字幕女同| 亚洲欧美春色| 亚洲欧美不卡| 欧美影视一区| 中文久久精品| 美乳少妇欧美精品| 欧美一区二区网站| 欧美日韩三区| 亚洲国产日韩综合一区| 国产尤物精品| 亚洲综合二区| 亚洲免费在线播放| 久久深夜福利免费观看| 亚洲自拍偷拍网址| 欧美日韩高清在线观看| 欧美暴力喷水在线| 国产一区白浆| 中文久久精品| 亚洲一区bb| 欧美日韩卡一卡二| 欧美jizzhd精品欧美喷水| 国产亚洲精品久久久久婷婷瑜伽| 一级日韩一区在线观看| 日韩五码在线| 欧美成人一区二区| 久久资源在线| 亚洲第一色在线| 久久国产精品一区二区三区| 久久精品五月| 黑人巨大精品欧美一区二区| 性欧美1819性猛交| 欧美影院午夜播放| 国产精品亚洲综合一区在线观看| 一区二区三区产品免费精品久久75| 亚洲精品综合久久中文字幕| 另类成人小视频在线| 嫩草国产精品入口| 亚洲激情第一区| 欧美日韩第一页| 在线一区日本视频| 亚洲五月婷婷| 国产精品美女999| 午夜欧美不卡精品aaaaa| 欧美一区三区二区在线观看| 国产精品资源在线观看| 亚洲欧美一级二级三级| 性刺激综合网| 国产精品亚洲综合色区韩国| 午夜精彩视频在线观看不卡 | 欧美三级网址| 亚洲婷婷免费| 久久www成人_看片免费不卡| 国语自产精品视频在线看| 久久经典综合| 亚洲电影av在线| 亚洲美女性视频| 国产精品v片在线观看不卡 | 亚洲欧美成人| 国内在线观看一区二区三区| 久久香蕉国产线看观看av| 亚洲高清在线视频| 亚洲在线1234| 激情六月婷婷综合| 欧美日本中文字幕| 亚洲欧美激情在线视频| 久久久久综合| 亚洲视频中文字幕| 精品va天堂亚洲国产| 欧美日韩视频免费播放| 亚洲在线观看免费| 欧美va天堂在线| 亚洲欧美另类久久久精品2019| 国产精品网站在线| 久久亚洲国产成人| 99re6热在线精品视频播放速度| 久久久久欧美精品| 9色国产精品| 黄色成人av在线| 欧美午夜一区| 欧美激情bt| 久久精品一区蜜桃臀影院| 夜夜精品视频| 欧美jizz19性欧美| 新片速递亚洲合集欧美合集| 99视频+国产日韩欧美| 一区二区亚洲精品国产| 国产精品亚洲一区| 欧美吻胸吃奶大尺度电影| 国产欧美视频一区二区| 亚洲国产电影| 久久久久青草大香线综合精品| 亚洲一区二区在线| 99这里只有久久精品视频| 又紧又大又爽精品一区二区|