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

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>
            亚洲一二三区精品| 久久国产精品一区二区三区| 欧美www视频| 亚洲精品一级| 亚洲黄色小视频| 性娇小13――14欧美| 韩国欧美一区| 麻豆久久久9性大片| 久久综合图片| 一区二区三区毛片| 亚洲欧美日韩精品久久| 精品99一区二区三区| 欧美 日韩 国产 一区| 欧美精品九九| 亚洲制服av| 久久人人97超碰精品888| 亚洲精品女av网站| 亚洲婷婷国产精品电影人久久 | 欧美激情一区二区三区不卡| 欧美精品一区二| 欧美自拍偷拍午夜视频| 国产精品久久久久久久久久尿| 欧美日韩精品在线观看| 欧美在线综合视频| 欧美高清视频www夜色资源网| 亚洲欧美韩国| 久久天天躁夜夜躁狠狠躁2022 | 樱花yy私人影院亚洲| 亚洲欧洲一区二区天堂久久| 国产欧美日韩在线播放| 欧美成人午夜激情在线| 国产精品青草综合久久久久99| 久久阴道视频| 国产乱理伦片在线观看夜一区| 欧美成人精品一区二区三区| 欧美视频免费看| 亚洲二区视频| 国产综合欧美| 一区二区三欧美| 亚洲精品国产精品乱码不99按摩| 亚洲一级电影| 在线午夜精品| 欧美二区乱c少妇| 久久影院午夜论| 国产精品亚洲综合色区韩国| 亚洲靠逼com| 最新69国产成人精品视频免费 | 亚洲电影中文字幕| 国产又爽又黄的激情精品视频| 99成人精品| 最新中文字幕亚洲| 久久婷婷亚洲| 久久久www成人免费精品| 欧美午夜宅男影院在线观看| 欧美国产视频一区二区| 一区二区亚洲精品| 国产日韩欧美二区| 久久婷婷成人综合色| 国产美女精品在线| 日韩亚洲在线观看| 一本色道久久综合亚洲精品婷婷 | 一道本一区二区| 欧美激情国产高清| 亚洲国产精品一区二区www在线| 影音先锋久久| 久久综合狠狠| 欧美激情导航| 亚洲最新色图| 欧美日韩免费视频| 亚洲免费精品| 亚洲精品美女久久久久| 欧美黄色一级视频| 亚洲日本电影| 日韩网站免费观看| 欧美三日本三级三级在线播放| 亚洲精品一二三| 亚洲一区二区高清| 国产精品麻豆成人av电影艾秋| 亚洲一区二区三区免费观看 | 亚洲经典视频在线观看| 欧美福利一区| 亚洲视频一区| 欧美在线观看视频| 在线不卡a资源高清| 欧美a一区二区| 99re在线精品| 欧美在线播放高清精品| 一区二区三区在线免费视频| 欧美成人日本| 亚洲一二三区视频在线观看| 久久久午夜电影| 制服丝袜亚洲播放| 国产精品裸体一区二区三区| 久久成人精品| 亚洲国产激情| 午夜精品福利一区二区三区av| 国产主播喷水一区二区| 欧美成人一区二免费视频软件| 亚洲美洲欧洲综合国产一区| 久久狠狠久久综合桃花| 亚洲精品中文字幕有码专区| 欧美视频亚洲视频| 亚洲欧美日韩一区在线| 免费成人av资源网| 一区二区三区**美女毛片| 国产一区二区日韩精品欧美精品| 欧美肥婆在线| 久久精品毛片| 亚洲一区二区在线视频| 久久人人爽人人| 一区二区不卡在线视频 午夜欧美不卡在 | 亚洲欧美日韩爽爽影院| 91久久在线视频| 久久精品国产精品亚洲| 一区二区三区波多野结衣在线观看| 国产亚洲欧洲一区高清在线观看| 欧美精品网站| 久久全国免费视频| 午夜欧美大片免费观看 | 欧美国产一区视频在线观看| 欧美一级精品大片| 亚洲视频1区2区| 亚洲精品美女免费| 亚洲国产成人在线| 国产在线播精品第三| 欧美日韩综合在线| 欧美 日韩 国产一区二区在线视频| 亚洲自拍偷拍一区| 亚洲美女电影在线| 亚洲电影免费观看高清完整版在线 | 国产精品欧美精品| 欧美日韩第一页| 欧美成人精品激情在线观看| 欧美亚洲综合在线| 性色av一区二区三区在线观看| 亚洲国产日日夜夜| 亚洲二区视频| 亚洲欧洲精品一区二区三区波多野1战4| 猛男gaygay欧美视频| 久久久综合网站| 久久婷婷激情| 久久婷婷国产麻豆91天堂| 久久亚洲精品视频| 美女免费视频一区| 久久精品二区三区| 久久色中文字幕| 免费亚洲一区| 欧美高清在线一区二区| 欧美激情亚洲| 亚洲久久一区二区| 一本大道久久a久久综合婷婷| 99精品视频一区| 一区二区三区高清| 最新国产成人av网站网址麻豆| 亚洲国产精品成人精品| 91久久在线视频| 亚洲视频在线观看一区| 亚洲欧美三级在线| 久久国产精品99国产精| 久久er精品视频| 久久综合网hezyo| 欧美人在线观看| 国产精品美女久久久久av超清 | 亚洲嫩草精品久久| 性做久久久久久免费观看欧美| 亚洲免费视频观看| 久久riav二区三区| 狂野欧美激情性xxxx欧美| 欧美高清在线视频观看不卡| 亚洲精品老司机| 性欧美videos另类喷潮| 美玉足脚交一区二区三区图片| 欧美日本在线观看| 国产午夜久久久久| 日韩视频在线永久播放| 欧美一级一区| 亚洲黄页视频免费观看| 午夜久久电影网| 欧美日本精品一区二区三区| 国产区欧美区日韩区| 亚洲另类黄色| 欧美一区二区三区四区高清| 欧美不卡在线| 亚洲午夜精品网| 欧美18av| 国产尤物精品| 亚洲欧美日韩国产综合在线 | 国产精品99久久久久久www| 欧美一区二区视频在线观看| 欧美激情精品久久久久久| 国产一区二区三区日韩欧美| 亚洲日韩中文字幕在线播放| 欧美影视一区| 亚洲美女黄色| 欧美成人在线免费视频| 国产午夜精品一区理论片飘花| 亚洲一级在线观看| 亚洲国产精品久久| 久久高清福利视频| 国产女主播一区二区|