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

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>
            国产欧美日韩亚洲精品| 亚洲国产精品一区在线观看不卡| 鲁鲁狠狠狠7777一区二区| 欧美三级午夜理伦三级中视频| 免费在线观看一区二区| 国产日本欧美一区二区三区在线| 日韩视频免费看| 亚洲美女黄色片| 女同一区二区| 亚洲电影自拍| 国精产品99永久一区一区| 亚洲一区精品在线| 亚洲欧美日韩国产综合在线| 欧美精品一区二区三区在线看午夜| 欧美二区视频| 亚洲欧洲日本在线| 欧美1区视频| 亚洲欧洲精品一区| 亚洲免费av电影| 欧美日韩高清一区| 亚洲精品国产精品国自产在线| 亚洲精品影院在线观看| 欧美肥婆在线| 亚洲精品欧美激情| 亚洲免费在线观看| 国产伦精品一区二区三区视频黑人 | 日韩午夜高潮| 亚洲夜晚福利在线观看| 欧美午夜精品一区二区三区| 一本久道久久综合中文字幕| 亚洲综合999| 国产一二三精品| 久久久久久一区二区| 欧美成人一区二免费视频软件| 亚洲风情在线资源站| 欧美电影免费观看网站| 91久久精品美女高潮| 亚洲女人天堂成人av在线| 国产三区精品| 久久琪琪电影院| 亚洲精品国产精品国自产观看浪潮 | 亚洲国产天堂网精品网站| 欧美aⅴ一区二区三区视频| 亚洲精品在线观看免费| 亚洲欧美日韩久久精品| 国内精品美女av在线播放| 欧美ed2k| 亚洲欧美日韩国产精品| 久久综合伊人77777麻豆| 99国产精品国产精品毛片| 国产精品欧美日韩久久| 免费不卡亚洲欧美| 亚洲少妇一区| 亚洲第一区在线观看| 亚洲在线观看视频| 亚洲福利视频在线| 国产精品日日摸夜夜摸av| 久久天堂国产精品| 亚洲无线观看| 欧美激情一区在线| 欧美淫片网站| 夜夜嗨网站十八久久| 韩国福利一区| 欧美午夜精品电影| 老司机免费视频一区二区三区| 一区二区激情| 欧美国内亚洲| 久久精品日韩| 亚洲视频 欧洲视频| 精品成人一区二区三区| 国产精品久久久久一区二区三区共| 久久精品在这里| 亚洲专区在线| 亚洲日本aⅴ片在线观看香蕉| 久久久久久综合| 亚洲一区在线播放| 亚洲伦理在线| 亚洲高清在线视频| 国产私拍一区| 国产精一区二区三区| 欧美日韩一区二区在线播放| 老司机午夜精品视频| 久久av二区| 午夜精品久久久久久久久久久| 亚洲乱码久久| 亚洲高清视频在线| 欧美波霸影院| 久久婷婷一区| 久久久亚洲国产天美传媒修理工| 亚洲欧美日本另类| 亚洲视频成人| 亚洲图片在区色| 一区二区三区四区在线| 亚洲精品国产精品乱码不99按摩| 永久免费精品影视网站| 国内伊人久久久久久网站视频| 国产日韩精品视频一区二区三区 | 欧美日韩国内自拍| 欧美激情在线播放| 欧美高清视频| 欧美精品一区三区在线观看| 嫩草国产精品入口| 欧美成人嫩草网站| 欧美jizz19hd性欧美| 蜜臀久久99精品久久久画质超高清| 久久乐国产精品| 久久综合福利| 欧美激情视频一区二区三区免费| 欧美不卡在线| 欧美日韩视频一区二区三区| 欧美日韩网址| 国产精品免费一区二区三区在线观看 | 久久久久国产免费免费| 久久久久久久久伊人| 麻豆久久婷婷| 欧美了一区在线观看| 欧美日韩一区高清| 国产区亚洲区欧美区| 激情久久婷婷| 亚洲精品视频在线看| 正在播放日韩| 欧美一区二区啪啪| 久久久免费精品| 亚洲高清二区| 在线综合欧美| 久久精品国产一区二区电影| 久久综合九色九九| 欧美日韩直播| 国产在线一区二区三区四区| 亚洲国产福利在线| 亚洲午夜电影在线观看| 久久久999精品视频| 亚洲激情另类| 亚洲综合国产激情另类一区| 久久久免费精品视频| 欧美伦理影院| 国语精品一区| 夜夜嗨一区二区| 久久国产福利| 亚洲人成在线观看| 欧美一区二区三区婷婷月色 | 欧美激情1区2区| 国产伦精品一区二区三区在线观看 | 欧美日韩亚洲在线| 韩国一区二区三区在线观看| 日韩视频免费观看| 久久精品国产第一区二区三区最新章节| 欧美不卡激情三级在线观看| 一区二区三区国产在线观看| 久久综合成人精品亚洲另类欧美| 国产精品国产三级国产普通话99 | 狠狠色噜噜狠狠色综合久 | 欧美成人tv| 亚洲欧美日韩精品久久亚洲区 | 久久亚洲风情| 国产欧美日韩精品在线| 99国内精品久久| 久久这里有精品视频| 亚洲午夜影视影院在线观看| 欧美成人免费网站| 红桃视频一区| 欧美一区二区视频免费观看 | 久久久久国产一区二区三区四区 | 亚洲精品免费在线播放| 久久久亚洲一区| 亚洲一区二区在线观看视频| 欧美伦理视频网站| 亚洲精品国精品久久99热一| 久久亚洲高清| 亚洲欧美日韩一区二区| 欧美日韩综合不卡| 日韩小视频在线观看专区| 免费一级欧美片在线观看| 小黄鸭视频精品导航| 欧美性淫爽ww久久久久无| 99国产精品久久久久久久久久| 欧美3dxxxxhd| 久久天堂国产精品| 在线观看欧美成人| 麻豆精品精华液| 久久福利精品| 精品动漫3d一区二区三区| 久久精品99国产精品日本| 在线综合+亚洲+欧美中文字幕| 欧美国产日韩一区| 亚洲伦理在线观看| 亚洲国产日韩一级| 欧美中文字幕第一页| 国产亚洲精品aa| 久久视频在线看| 欧美亚洲一区二区在线| 欧美区高清在线| 99国产精品视频免费观看| 亚洲精品在线三区| 欧美色网在线| 欧美淫片网站| 久久天堂国产精品| 亚洲精品影院在线观看| 日韩视频一区二区三区| 国产精品久久久一本精品|