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

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 閱讀(566) 評論(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级一区| 亚洲一卡久久| 欧美a级片网站| 国内精品视频在线播放| 亚洲中无吗在线| 亚洲一区二区三区免费视频| 欧美电影在线观看| 国产深夜精品福利| 亚洲一卡久久| 亚洲欧洲日韩在线| 久久久999精品视频| 国产老肥熟一区二区三区| 欧美一区二区三区在线观看视频| 亚洲精品美女在线观看播放| 久久久久欧美精品| 国产拍揄自揄精品视频麻豆| 亚洲特级毛片| 亚洲国产精品久久久| 久久国产综合精品| 国产亚洲欧美激情| 欧美一区影院| 蜜臀va亚洲va欧美va天堂| 国产一区二区三区久久悠悠色av | 欧美午夜激情小视频| 亚洲福利在线看| 裸体一区二区| 久久久久久久91| 一本色道久久加勒比88综合| 亚洲国产精品一区在线观看不卡 | 欧美成人午夜视频| 亚洲一区区二区| 美国成人直播| 欧美在线观看天堂一区二区三区| 久久久久久久综合色一本| 亚洲一区精品视频| 欧美77777| 久久米奇亚洲| 久久视频精品在线| 亚洲黄色影院| 亚洲美女视频网| 国产精品久久99| 性色av一区二区三区在线观看| 99伊人成综合| 亚洲国产99精品国自产| 亚洲欧美日韩视频一区| 黑人一区二区三区四区五区| 蜜臀av一级做a爰片久久| 美女图片一区二区| 欧美专区日韩专区| 久久综合网络一区二区| 亚洲精品欧美在线| 久久久久久有精品国产| 欧美一区2区三区4区公司二百| 欧美日韩精品免费观看视一区二区| 亚洲一区二区动漫| 欧美激情精品久久久久久变态| 亚洲在线成人精品| 欧美老女人xx| 久久久久高清| 欧美大片国产精品| 欧美激情久久久久久| 欧美午夜不卡视频| 999亚洲国产精| 在线一区视频| 免费观看国产成人| 欧美成人激情视频| 91久久精品国产91久久性色tv| 一本大道久久精品懂色aⅴ| 亚洲理论在线| 久久精品国产99精品国产亚洲性色| 亚洲欧美一区二区三区在线| 免费不卡在线视频| 亚洲电影第1页| 亚洲精品在线观看免费| 欧美激情亚洲综合一区| 久久嫩草精品久久久精品| 国产性色一区二区| 久久躁日日躁aaaaxxxx| 欧美jizzhd精品欧美巨大免费| 亚洲电影免费观看高清完整版在线观看| 日韩亚洲欧美综合| 亚洲欧美在线免费观看| 国产一区亚洲| 老司机精品视频网站| 91久久一区二区| 午夜亚洲精品| 亚洲成人在线免费| 欧美日韩在线播放三区四区| 欧美国产日韩xxxxx| 亚洲色图自拍| 国产午夜精品美女毛片视频| 久久久久久久久久码影片| 亚洲国产婷婷| 午夜亚洲性色福利视频| 在线观看国产成人av片| 久久国产日本精品| 亚洲激情不卡| 久久久久久电影| 亚洲精品视频在线| 国产欧美精品日韩| 免费在线观看一区二区| 亚洲欧美日韩综合国产aⅴ| 欧美激情中文字幕乱码免费| 亚洲欧美日韩精品久久| 国产精品vvv| 美女精品网站| 亚洲私拍自拍| 亚洲国产精品专区久久| 久久精品国产99国产精品| 国产精品自在线| 欧美岛国在线观看| 香蕉成人伊视频在线观看| 久久精品1区| 一区二区三区欧美成人| 在线观看av不卡| 国产欧美亚洲精品| 欧美日韩国产丝袜另类| 久久午夜精品| 欧美在线观看日本一区| 模特精品裸拍一区| 欧美一二三视频| 9人人澡人人爽人人精品| 一区二区亚洲精品| 欧美黄色免费| 久久人人超碰| 欧美一区二区三区视频| 欧美成黄导航| 久久久久久黄| 久久成人亚洲| 午夜精品久久久久久| 在线一区二区日韩| 99在线热播精品免费99热| 亚洲国产成人精品久久| 国内久久视频| 精品999在线观看| 好吊妞这里只有精品| 国产日韩亚洲欧美| 国产一区二区三区免费不卡 | 国产精品国产三级国产普通话三级| 欧美sm视频| 美女脱光内衣内裤视频久久网站| 久久精品日韩欧美| 久久免费午夜影院| 久久综合狠狠综合久久综合88| 久久激情视频| 久久久噜噜噜久久| 久久亚洲国产精品一区二区| 久久久久久尹人网香蕉| 卡通动漫国产精品| 你懂的成人av| 欧美日韩精品二区| 国产精品你懂的在线| 久久深夜福利免费观看| 久久久久网站| 欧美激情一区二区三区在线视频观看| 美日韩精品视频| 欧美日韩高清在线观看| 国产精品mm| 国产一区二区精品久久99| 激情久久中文字幕| 亚洲精品欧美日韩| 亚洲欧美日本精品| 久久视频这里只有精品| 午夜欧美精品| 久久久夜色精品亚洲| 欧美激情偷拍| 亚洲图片自拍偷拍| 久久精品视频网| 欧美了一区在线观看| 国产伦精品一区二区三区四区免费 | 欧美性色aⅴ视频一区日韩精品| 国产精品久久久久999| 国产亚洲综合在线| 亚洲免费激情| 久久av一区二区三区| 欧美高清不卡| 蜜桃视频一区| 一区二区三区国产精品| 亚洲精品男同| 小黄鸭精品aⅴ导航网站入口 | 亚洲黄网站黄| 亚洲在线一区二区| 最新国产成人av网站网址麻豆| 亚洲精品你懂的| 欧美高清在线视频观看不卡| 99国产精品久久久| 久久成人精品无人区| 欧美久久在线| 亚洲国产精品福利| 性欧美暴力猛交另类hd| 亚洲韩日在线| 久久久久久穴| 国产精品人人爽人人做我的可爱| 国产精品极品美女粉嫩高清在线 | 欧美人成在线视频|