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

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>
            久久香蕉国产线看观看av| 亚洲精品永久免费| 亚洲一区免费网站| 国产精品一二一区| 欧美在线www| 欧美专区在线观看| 一区在线免费| 亚洲二区视频在线| 免费毛片一区二区三区久久久| 狠狠综合久久| 快射av在线播放一区| 久久一区二区精品| 亚洲网址在线| 香蕉乱码成人久久天堂爱免费| 尤物99国产成人精品视频| 亚洲第一黄网| 国产精品久久久久久模特| 久久国产精品99久久久久久老狼| 亚洲在线中文字幕| 在线观看一区欧美| 日韩一级免费观看| 国内精品久久久久久久97牛牛| 欧美成人免费小视频| 国产精品v欧美精品v日韩精品| 久久国产免费看| 欧美成人午夜免费视在线看片 | 欧美日韩1区2区| 性久久久久久| 女女同性精品视频| 久久国产精品毛片| 欧美精品999| 久久综合五月| 欧美性开放视频| 欧美 日韩 国产 一区| 欧美日韩一区二区欧美激情| 久久婷婷人人澡人人喊人人爽| 欧美日韩国产首页| 欧美福利电影网| 国产日韩欧美精品在线| 亚洲精品少妇网址| 亚洲国产精品热久久| 午夜亚洲福利| 亚洲欧美成人一区二区三区| 欧美高清视频一区| 久久天堂av综合合色| 国产精品女主播在线观看 | 亚洲免费激情| 欧美综合激情网| 亚洲欧美在线aaa| 欧美日韩精品一区| 亚洲国产一区在线| 韩国女主播一区| 欧美一级淫片播放口| 亚洲影音一区| 欧美天天综合网| 亚洲日韩欧美视频一区| 精品白丝av| 欧美资源在线| 久久免费精品日本久久中文字幕| 国产精品日韩欧美一区二区| 亚洲精品免费一二三区| 91久久精品国产91久久性色tv| 久久米奇亚洲| 欧美激情免费在线| 亚洲三级色网| 欧美福利视频| 日韩视频在线免费| 亚洲网站视频| 国产精品久久久久久av下载红粉| 亚洲伦理精品| 亚洲一区二区三区在线看| 欧美一区二区久久久| 午夜欧美精品| 久久久久久久成人| 在线播放豆国产99亚洲| 久久精品亚洲精品国产欧美kt∨| 久久精品国产亚洲一区二区三区 | 久久婷婷蜜乳一本欲蜜臀| 久久亚洲精品伦理| 亚洲国产成人不卡| 欧美美女福利视频| 一本色道**综合亚洲精品蜜桃冫| 亚洲性图久久| 国产手机视频精品| 久久米奇亚洲| 日韩亚洲视频| 久久黄金**| 亚洲国产高清一区| 欧美日韩高清在线一区| 亚洲欧美不卡| 欧美国产亚洲视频| 一区二区欧美日韩视频| 国产精品色一区二区三区| 欧美在线免费看| 亚洲福利视频网| 亚洲午夜视频| 激情伊人五月天久久综合| 欧美精品不卡| 亚洲欧美国产视频| 亚洲人成精品久久久久| 欧美一区二区视频网站| 亚洲国产精品123| 国产精品久久77777| 欧美在线免费| 99视频精品在线| 久久资源在线| 亚洲视频网在线直播| 在线不卡a资源高清| 欧美午夜不卡视频| 美日韩精品免费观看视频| 一本大道久久a久久精品综合| 久久九九精品| 亚洲视频二区| 亚洲欧洲日本国产| 国产一区二区三区在线观看免费视频| 欧美va天堂| 久久精品99| 亚洲一区二区三区激情| 亚洲国产欧美不卡在线观看| 欧美中文字幕在线| 中文在线资源观看视频网站免费不卡| 狠狠色狠狠色综合系列| 国产精品入口麻豆原神| 欧美精品一级| 久久天天狠狠| 久久精品亚洲乱码伦伦中文 | 欧美激情精品| 久久久久久久综合色一本| 亚洲综合日本| 在线性视频日韩欧美| 亚洲人成亚洲人成在线观看| 国产一区二区三区视频在线观看| 欧美视频中文在线看| 欧美区一区二| 欧美日韩二区三区| 欧美成人在线网站| 老司机一区二区| 久久看片网站| 久久躁狠狠躁夜夜爽| 久久激情视频| 欧美在线观看网站| 欧美一区二区三区免费观看 | 欧美激情第二页| 久久久综合精品| 久久久久久电影| 久久精品国产99| 久久久精品五月天| 开心色5月久久精品| 老**午夜毛片一区二区三区| 久久一区二区三区四区| 噜噜噜久久亚洲精品国产品小说| 久久中文字幕一区二区三区| 美女网站在线免费欧美精品| 奶水喷射视频一区| 亚洲国产精品视频| 亚洲精品久久7777| 夜夜嗨av一区二区三区免费区| 亚洲深夜影院| 香蕉国产精品偷在线观看不卡| 欧美一区二区在线免费观看 | 亚洲国产天堂久久综合| 亚洲精品一区在线观看香蕉| 99在线热播精品免费99热| 亚洲天堂成人在线视频| 亚洲综合日韩在线| 久久久久久成人| 欧美精品一区二区蜜臀亚洲| 欧美天堂在线观看| 红桃视频国产精品| 亚洲片在线观看| 亚洲一区二区在线看| 久久久久久久久岛国免费| 欧美国产高潮xxxx1819| 亚洲裸体俱乐部裸体舞表演av| 在线亚洲电影| 久久国产精品免费一区| 欧美黄色一区| 国产欧美日韩三区| 亚洲国产一区二区三区在线播 | 欧美在线播放高清精品| 美日韩精品视频| 亚洲美女毛片| 久久高清国产| 欧美日韩色综合| 国产综合自拍| 亚洲视频一区| 久久综合婷婷| 亚洲夜间福利| 你懂的国产精品| 国产日韩精品在线| 9l视频自拍蝌蚪9l视频成人| 久久九九免费视频| 一区二区三区av| 免费毛片一区二区三区久久久| 国产精品一区二区在线观看网站 | 国产午夜精品理论片a级探花 | 一区二区三区高清在线观看| 久久久综合免费视频| 亚洲综合不卡| 欧美日韩国产成人在线免费|