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

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>
            免费看成人av| 亚洲精品日韩久久| 欧美一区二区三区免费观看| 国产精品久久一卡二卡| 亚洲影视中文字幕| 亚洲砖区区免费| 国产香蕉97碰碰久久人人| 久久精品视频在线免费观看| 欧美中文日韩| 亚洲人成绝费网站色www| 亚洲激情视频网站| 欧美日韩一二三区| 性感少妇一区| 久久一区亚洲| 亚洲主播在线播放| 欧美中文字幕视频| 亚洲精品一区二| 在线一区二区三区做爰视频网站| 国产精品美女诱惑| 免费观看在线综合色| 欧美日韩精品免费观看视频完整| 午夜在线a亚洲v天堂网2018| 久久久国产精品一区二区三区| 亚洲国产高清aⅴ视频| 99热在线精品观看| 狠狠综合久久av一区二区老牛| 亚洲国产欧美一区| 国产精品美女主播在线观看纯欲| 久久频这里精品99香蕉| 欧美精品日韩| 久久最新视频| 国产精品毛片大码女人| 欧美成人亚洲成人| 国产区精品视频| 亚洲欧洲另类| 激情成人中文字幕| 亚洲图片欧洲图片日韩av| 亚洲国产小视频| 亚洲免费婷婷| 亚洲视频香蕉人妖| 美女久久一区| 久久久久久9| 国产精品va在线播放我和闺蜜| 欧美成人精品影院| 国产一区二区三区日韩| 在线亚洲激情| 一区二区免费在线观看| 久久青草欧美一区二区三区| 性久久久久久久| 欧美视频中文在线看| 欧美成年人在线观看| 国产视频欧美视频| 亚洲一区二区三| 亚洲综合色视频| 欧美日韩国产高清| 亚洲国产小视频在线观看| 在线观看视频一区二区| 欧美一级播放| 久久精品欧美日韩精品| 国产欧美日韩不卡| 午夜伦理片一区| 欧美专区福利在线| 国产麻豆91精品| 国模 一区 二区 三区| 香蕉av777xxx色综合一区| 欧美一级淫片aaaaaaa视频| 国产精品美女久久久久av超清| 亚洲理论电影网| 亚洲天堂第二页| 国产精品久久久久久亚洲调教 | 韩国欧美国产1区| 羞羞答答国产精品www一本 | 亚洲成人在线观看视频| 久久福利精品| 欧美xx69| 日韩特黄影片| 欧美午夜女人视频在线| 亚洲一区二区三区四区视频| 欧美一区精品| 在线免费高清一区二区三区| 牛人盗摄一区二区三区视频| 亚洲观看高清完整版在线观看| 亚洲人成亚洲人成在线观看图片| 欧美国产欧美综合| 一区二区高清在线| 久久久国产成人精品| 亚洲国产导航| 欧美体内谢she精2性欧美| 黄色精品网站| 国产精品jvid在线观看蜜臀| 亚洲图色在线| 好吊日精品视频| 欧美在线免费观看视频| 女人香蕉久久**毛片精品| 亚洲福利视频在线| 欧美日韩综合在线| 亚洲欧美日韩一区二区| 欧美国产日韩一区二区| 在线亚洲自拍| 激情久久五月天| 欧美日韩直播| 久久精品成人欧美大片古装| 亚洲国产你懂的| 久久成人免费日本黄色| 亚洲国产二区| 国产乱码精品一区二区三区不卡| 久久久亚洲一区| 亚洲最新在线| 欧美大片在线观看一区二区| 亚洲欧美成人综合| 亚洲国产美女精品久久久久∴| 欧美午夜电影网| 免费观看日韩av| 午夜在线观看欧美| 99pao成人国产永久免费视频| 久久久999| 亚洲免费在线观看视频| 亚洲第一精品夜夜躁人人爽| 国产精品swag| 欧美麻豆久久久久久中文| 久久久久久久久久久久久女国产乱| 亚洲另类春色国产| 欧美激情久久久久| 久久男人资源视频| 久久狠狠婷婷| 午夜精品亚洲| 一二三四社区欧美黄| 亚洲黄色高清| 国内成人精品一区| 国产欧美在线播放| 国产精品一区二区欧美| 欧美午夜a级限制福利片| 欧美精品18+| 欧美~级网站不卡| 久久伊人免费视频| 久久久午夜视频| 久久国产日韩| 亚洲欧美区自拍先锋| 亚洲天堂男人| 亚洲一区在线免费观看| 国产日韩欧美高清免费| 国产精品视频专区| 欧美喷水视频| 欧美精品v日韩精品v韩国精品v| 久久久人成影片一区二区三区| 久久爱www.| 久久精品女人的天堂av| 久久成人免费| 久久婷婷综合激情| 久久久欧美一区二区| 久久久久一本一区二区青青蜜月| 久久精品国产在热久久| 久久av免费一区| 久久午夜精品| 免费观看不卡av| 欧美日韩国产欧| 欧美三级电影一区| 国产精品美女一区二区在线观看| 欧美日韩亚洲一区二区三区在线观看 | 亚洲嫩草精品久久| 亚洲综合欧美| 销魂美女一区二区三区视频在线| 性欧美18~19sex高清播放| 久久不射中文字幕| 久久先锋影音av| 欧美久久久久免费| 国产精品久久久久久久电影| 国产日韩综合一区二区性色av| 狠狠色综合色区| 亚洲欧洲日夜超级视频| 亚洲一区影音先锋| 久久国产欧美日韩精品| 欧美电影打屁股sp| 一本色道久久88亚洲综合88| 午夜免费久久久久| 欧美jizzhd精品欧美喷水| 欧美日韩精品一区视频| 国产日韩欧美综合在线| 亚洲日本中文| 性娇小13――14欧美| 欧美激情视频在线播放 | 亚洲精品男同| 亚洲欧美日韩国产综合精品二区| 久久精品国产精品亚洲| 欧美大尺度在线| 国产精品视频网站| 亚洲黄色在线视频| 亚洲免费影视第一页| 欧美激情1区2区3区| 亚洲一区二区在线看| 免费欧美视频| 国产欧美日韩综合一区在线播放| 亚洲欧洲精品一区| 久久国产精品久久久| 亚洲国产精品久久久久| 亚洲欧美一区二区激情| 欧美日韩精品不卡| 一区二区视频欧美| 欧美一区二区视频在线| 亚洲精选大片|