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

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>
            欧美影院一区| 午夜精品免费在线| 欧美日韩国产成人在线观看| 亚洲欧洲日产国产网站| 亚洲国产精品va在线看黑人动漫| 老司机免费视频久久| 亚洲精选视频在线| 亚洲特色特黄| 好男人免费精品视频| 欧美激情精品久久久久久蜜臀| 欧美成人国产va精品日本一级| 9l视频自拍蝌蚪9l视频成人| 日韩一级二级三级| 国产欧美日韩视频一区二区| 老司机精品福利视频| 欧美激情一区三区| 久久精品国产一区二区三区免费看| 久久国产手机看片| 一区二区三区av| 欧美在线视频日韩| 日韩一级黄色大片| 欧美一级片一区| 亚洲欧洲日本国产| 欧美亚洲视频在线观看| 亚洲人久久久| 欧美伊久线香蕉线新在线| 亚洲看片一区| 欧美有码在线视频| 亚洲一区二区高清| 狂野欧美激情性xxxx| 亚洲欧美激情视频在线观看一区二区三区 | 韩国女主播一区| 亚洲精品国产精品乱码不99按摩 | 国产精品视频99| 亚洲福利视频免费观看| 国产欧美精品一区二区色综合 | 久久综合福利| 国产精品视区| 亚洲美女诱惑| 亚洲全部视频| 久久久久一区二区三区四区| 亚洲一区二区三| 欧美激情综合网| 免费久久精品视频| 国产亚洲欧美日韩日本| 一本色道久久综合亚洲精品婷婷| 亚洲激情成人在线| 久久久国产精品一区| 欧美一区二区三区免费观看视频| 欧美激情区在线播放| 欧美激情乱人伦| 一区二区三区亚洲| 久久久久久久久久久一区| 欧美影院在线| 国产日韩久久| 欧美一区二区三区婷婷月色| 亚洲欧美日韩一区二区三区在线观看| 欧美激情久久久| 亚洲黄色性网站| 亚洲日韩欧美视频| 欧美激情1区2区| 亚洲国产精品高清久久久| 亚洲激情黄色| 欧美激情一区二区三区在线视频观看 | 欧美精品xxxxbbbb| 亚洲国产你懂的| 亚洲精品免费在线观看| 欧美ab在线视频| 亚洲区中文字幕| 99视频精品| 欧美色欧美亚洲另类七区| 99精品国产热久久91蜜凸| 亚洲午夜精品一区二区三区他趣| 欧美视频一区二区三区四区| 中文在线资源观看网站视频免费不卡| 亚洲一区二区在线| 国产精品一二一区| 欧美一区二区高清| 美国十次了思思久久精品导航| 在线成人小视频| 欧美激情日韩| 宅男噜噜噜66一区二区66| 午夜视频一区二区| 一区在线观看| 欧美日韩999| 亚洲一区二区少妇| 美女久久网站| 中文在线不卡视频| 国产亚洲精品成人av久久ww| 久久久免费av| 一本色道久久| 久久免费视频在线观看| 亚洲人成人一区二区在线观看| 欧美日韩精品一区二区三区| 亚洲欧美日韩一区在线| 欧美国产激情| 性久久久久久久久久久久| 在线观看的日韩av| 欧美视频一区二区在线观看| 久久精品女人| 亚洲最新在线| 欧美成人黑人xx视频免费观看| 亚洲婷婷国产精品电影人久久| 国产亚洲激情在线| 欧美日韩黄视频| 久久久久成人精品免费播放动漫| 亚洲精品乱码久久久久久蜜桃91| 久久成人国产| 亚洲私人影吧| 亚洲国产精品一区在线观看不卡| 欧美视频免费在线| 乱人伦精品视频在线观看| 亚洲免费在线看| 亚洲美女中文字幕| 欧美jizzhd精品欧美喷水| 新狼窝色av性久久久久久| 夜夜精品视频| 亚洲国产专区| 狠狠色综合日日| 国产欧美日韩在线观看| 欧美日韩精品国产| 欧美成人免费全部| 久久久青草青青国产亚洲免观| 亚洲影院一区| 亚洲午夜视频在线观看| 亚洲精品视频在线观看网站 | 亚洲制服少妇| 一区二区日韩免费看| 亚洲美女视频在线观看| 亚洲激情偷拍| 91久久精品一区二区三区| 精久久久久久| 激情国产一区二区| 国产综合欧美| 韩日精品中文字幕| 国产中文一区二区| 国产亚洲欧美一区在线观看| 国产精品视频男人的天堂| 国产精品久久久| 国产精品久久久久久模特| 久久精品伊人| 久久精品国产99国产精品澳门| 午夜久久一区| 欧美中文字幕在线观看| 久久精品国产亚洲a| 久久噜噜噜精品国产亚洲综合| 久久精品一区四区| 麻豆精品传媒视频| 欧美激情黄色片| 亚洲日本aⅴ片在线观看香蕉| 亚洲国产合集| 99re热精品| 亚洲免费视频成人| 久久gogo国模啪啪人体图| 欧美专区在线播放| 久久综合国产精品台湾中文娱乐网| 久久综合久久综合这里只有精品| 久久亚洲免费| 欧美日韩激情小视频| 国产精品综合网站| 韩国女主播一区| 亚洲精品黄网在线观看| 这里只有精品丝袜| 欧美在线视频日韩| 欧美va亚洲va国产综合| 91久久精品国产91久久性色| 日韩一区二区免费高清| 亚洲欧美日韩爽爽影院| 久久综合国产精品| 欧美亚州一区二区三区 | 国产精品jvid在线观看蜜臀| 国产精品视频久久| 亚洲第一主播视频| 中日韩视频在线观看| 欧美在线视频导航| 91久久精品国产| 久久高清国产| 欧美日韩喷水| 一区二区在线观看视频在线观看| 一本久久a久久免费精品不卡| 性欧美xxxx大乳国产app| 欧美激情偷拍| 午夜免费电影一区在线观看| 欧美国产精品久久| 国产午夜精品一区二区三区视频 | 欧美电影免费观看大全| 一本色道久久综合| 久热精品视频在线观看| 国产精品高潮呻吟视频| 亚洲日韩视频| 久久一综合视频| 一本色道久久综合狠狠躁篇的优点| 久久久久久久尹人综合网亚洲| 欧美日韩在线免费视频| 亚洲激情视频在线| 巨乳诱惑日韩免费av| 亚洲欧美一区二区激情| 欧美日韩在线电影| 亚洲日本视频| 免费高清在线一区|