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

ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用鏈接

留言簿(24)

隨筆分類(332)

隨筆檔案(182)

FRIENDS

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

題目地址 :

http://poj.org/problem?id=2528

題目描述:

Mayor's posters
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 15722Accepted: 4444

Description

The 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. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules: 
  • Every candidate can place exactly one poster on the wall. 
  • All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown). 
  • The wall is divided into segments and the width of each segment is one byte. 
  • Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections. 
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall. 

Input

The first line of input contains a number c giving the number of cases that follow. The 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.

Output

For each input data set print the number of visible posters after all the posters are placed. 

The picture below illustrates the case of the sample input. 

Sample Input

1
5
1 4
2 6
8 10
3 4
7 10

Sample Output

4

 題目分析 :

代碼
/*
   線段樹 +  離散化
    
   好像記得暑假做 樹狀數(shù)組的時候 做過一個離散化的題目, 當(dāng)時是用2分查詢
   離散節(jié)點(diǎn)標(biāo)記的, 速度還是可以的, 不過那時對離散化也沒有什么概念, 大
   概是沒怎么接觸, 今天做了這道題目的時候,  也算是明白了 離散化 的基本
   意思,因?yàn)?nbsp;題目的 數(shù)據(jù)范圍很大 , 1- 10000000,直接線段樹的話, 先不說
   內(nèi)存會不會爆, 這么大的范圍估計(jì)也是 TLE了. 
   仔細(xì)讀題, 可以看到  1<= N <= 10000, 也就是說 最多只有 10000個點(diǎn), 如果
   每個點(diǎn)都不同, 那么最多也只有 20000 個數(shù)據(jù), 那么離散后的 范圍就相當(dāng)小;
   
   離散化 的大概思路 :   比如說給你一組 數(shù)據(jù) 1 4 1000 100000,  如果直接
                         開線段, 顯然是浪費(fèi), 那么我們只要 進(jìn)行 映射 :
                                1    1  
                                4    2
                             1000    3
                           100000    4
                         接下來 我們只要對 1 2 3 4 建立線段樹就行了 只需要
                         [1,4]的區(qū)間     
*/

/*
Mail to   : miyubai@gamil.com
Link      : 
http://www.cnblogs.com/MiYu  || http://m.shnenglu.com/MiYu
Author By : MiYu
Test      : 1
Complier  : g++ mingw32-3.4.2
Program   : 2528
Doc Name  : Mayor's posters
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include 
<fstream>
#include 
<sstream>
#include 
<algorithm>
#include 
<string>
#include 
<set>
#include 
<map>
#include 
<utility>
#include 
<queue>
#include 
<stack>
#include 
<list>
#include 
<vector>
#include 
<cstdio>
#include 
<cstdlib>
#include 
<cstring>
#include 
<cmath>
#include 
<ctime>
using namespace std;
int T, N, x, y;
map 
< intint > mp;
set <int> st;
map
<int,int>::iterator beg, end;
struct segtree {
       
int left, right,cov;
       
int mid () { return (left+right)>>1; }
}seg[
80010];
struct P {  //節(jié)點(diǎn)數(shù)據(jù) 
       int left, right;
}pp[
10010];
void creat ( int x, int y, int rt = 1 ) {
     seg[rt].left 
= x;
     seg[rt].right 
= y;
     seg[rt].cov 
= 0;
     
if ( x == y ) return ;
     
int mid = seg[rt].mid();
     creat ( x, mid, rt 
<< 1 );
     creat ( mid 
+ 1, y, rt << 1 | 1 );     
}
void insert ( int x, int y, int flag, int rt = 1 ) {
     
//如果線段被覆蓋, 直接標(biāo)記, 返回 
    if ( seg[rt].left == x && seg[rt].right == y ) {
        seg[rt].cov 
= flag;
        
return;   
    }    
    
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
    
if ( seg[rt].cov != -1 ) {  
       
//如果線段是被覆蓋的 , 標(biāo)記下傳, 同時自身標(biāo)記-1,表示有多個標(biāo)記 
        seg[LL].cov = seg[RR].cov = seg[rt].cov;
        seg[rt].cov 
= -1;   
    }
    
//遞歸 插入 
    if ( y <= mid ) insert ( x, y, flag, LL );
    
else if ( x > mid ) insert ( x, y, flag, RR );
    
else {
          insert ( x, mid, flag, LL );
          insert ( mid 
+ 1, y, flag, RR );     
    }
}
void query ( int x, int y, int rt = 1 ) {
    
// 線段被覆蓋 , 將覆蓋標(biāo)記 放入 set 
    if ( seg[rt].cov != -1 && seg[rt].left == x && seg[rt].right == y ) {
        st.insert ( seg[rt].cov );
        
return ;   
    }
else {//遞歸查詢 
          int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
          
if ( y <= mid ) query ( x, y, rt << 1 ); 
          
else if ( x > mid ) query ( x, y, rt << 1 | 1 );
          
else {
                query ( x, mid, LL );
                query ( mid 
+ 1, y, RR );     
          }
    }
}
void print () {
     
for ( set<int>::iterator it = st.begin(); it != st.end(); ++ it )
           cout 
<< *it << endl;     
}
int main ()
{
    scanf ( 
"%d"&T );
    creat ( 
120010 );
    
while ( T -- ) {
           mp.clear();
           st.clear (); 
           scanf ( 
"%d"&N );
           
for ( int i = 1; i <= N; ++ i ) {
                scanf ( 
"%d%d"&pp[i].left, &pp[i].right );
                 
//map 去重 
                mp[pp[i].left] = 88; mp[pp[i].right] = 88;    
           }      
           beg 
= mp.begin(), end = mp.end();
           
//因?yàn)閙ap 已經(jīng)自動排序了,所以直接從 1 --> N 開始標(biāo)記, 離散化 
           for ( int i = 1;beg != end; ++ beg, ++ i ) {         
                beg
->second = i;  
           }
           
//因?yàn)榫€段樹已經(jīng)建立好了, 所以沒必要每次都重建一次, 只要插入一條
           
//覆蓋所有區(qū)間的 底板 就行了 
           insert ( 1, N * 20 );
           
for ( int i = 1; i <= N; ++ i ) {
                
//用離散后的標(biāo)記 插入 線段 
                insert ( mp[pp[i].left], mp[pp[i].right], i );   
           }
           query ( 
1, N * 2 );
           
//print();
           int cnt = st.size();
           
if ( *st.begin() == 0 ) -- cnt; 
           printf ( 
"%d\n", cnt );
    }

    
return 0;
}

 

Feedback

# re: PKU 2528 POJ 2528 Mayor's posters ( 線段樹+離散化 ) ACM 2528 IN PKU  回復(fù)  更多評論   

2011-10-19 22:34 by wjjay
3
1 10
1 5
7 10
請問這組數(shù)據(jù)在你程序里跑出來的結(jié)果跟你手算的一樣么?
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            久久综合伊人77777蜜臀| 日韩视频国产视频| 欧美在线一区二区| 亚洲欧美日韩国产一区| 国产伦理一区| 久久综合狠狠综合久久综合88 | 亚洲欧美视频一区| 亚洲欧美日韩在线播放| 激情欧美日韩| 亚洲激情电影在线| 欧美日韩一区二区视频在线| 午夜一区不卡| 久久亚洲精品一区二区| 在线中文字幕一区| 性高湖久久久久久久久| 亚洲人体1000| 亚洲天堂黄色| 在线观看日韩av电影| 日韩一级片网址| 国产一区二区三区在线观看视频| 老牛影视一区二区三区| 亚洲欧美日本国产有色| 亚洲国产成人不卡| 欧美久久久久久蜜桃| 久久国产精品久久久久久久久久 | 99re8这里有精品热视频免费 | 亚洲欧美在线免费| 亚洲激情综合| 午夜日韩在线| 一区二区三区欧美激情| 久久精视频免费在线久久完整在线看| 日韩一级网站| 久久琪琪电影院| 欧美在线亚洲综合一区| 欧美极品一区二区三区| 久久久最新网址| 国产精品久久久久一区二区| 亚洲国产欧美一区| 国内精品久久久久久久影视蜜臀| 9久草视频在线视频精品| 亚洲福利视频网| 久久激情综合网| 亚洲欧美在线另类| 欧美日韩精品在线| 亚洲国产第一页| 经典三级久久| 新67194成人永久网站| 亚洲一区欧美二区| 欧美日韩在线视频首页| 亚洲黄色在线观看| 亚洲精品国产日韩| 欧美.www| 亚洲福利视频一区二区| 亚洲大片免费看| 久久久久久久久久久久久久一区| 久久国产精品99久久久久久老狼| 国产老肥熟一区二区三区| 中文一区二区在线观看| 亚洲影音一区| 欧美亚洲第一页| 亚洲色诱最新| 欧美一区二区女人| 国产日韩欧美精品一区| 欧美一级久久| 久久综合久久久| 亚洲国产精品v| 欧美二区在线看| 亚洲精品乱码久久久久久日本蜜臀| 91久久精品国产91性色| 欧美大片在线观看一区| 亚洲精品国产欧美| 亚洲一区二区三| 国产女优一区| 久久久另类综合| 亚洲精品1234| 亚洲一区在线直播| 国产偷久久久精品专区| 久久久久久国产精品mv| 亚洲黄色精品| 亚洲欧美国产不卡| 国外成人在线| 欧美华人在线视频| 宅男噜噜噜66一区二区66| 久久精品亚洲一区二区三区浴池| 国产专区一区| 欧美极品aⅴ影院| 亚洲欧美成人一区二区三区| 久久亚洲捆绑美女| 一区二区三区四区五区在线| 国产精品欧美日韩一区| 久久精品水蜜桃av综合天堂| 亚洲三级观看| 久久精品盗摄| 欧美一二三视频| 亚洲国产精品一区二区第四页av| 亚洲视频在线观看网站| 黄网站免费久久| 欧美日韩一区二区欧美激情| 欧美一区二区三区在线播放| 亚洲国产精品va在线看黑人动漫| 亚洲尤物在线| 亚洲福利久久| 国产视频在线观看一区二区| 欧美黑人在线观看| 欧美一区午夜视频在线观看| 亚洲国产欧美一区二区三区丁香婷 | 午夜国产欧美理论在线播放 | 久久躁狠狠躁夜夜爽| 中文亚洲免费| 亚洲高清免费在线| 国产日韩欧美精品综合| 欧美日韩一区视频| 欧美国产日韩精品免费观看| 久久精品国产精品亚洲精品| 一区二区三区精密机械公司| 亚洲第一黄网| 可以免费看不卡的av网站| 翔田千里一区二区| 在线亚洲自拍| 亚洲狼人精品一区二区三区| 在线观看亚洲视频| 国产亚洲精品久久久久婷婷瑜伽| 国产精品精品视频| 欧美日韩喷水| 欧美日韩三级电影在线| 欧美国内亚洲| 欧美成人免费网站| 久久这里有精品15一区二区三区| 欧美影片第一页| 亚洲欧美日韩国产| 亚洲一区二区三区777| 一区二区日韩精品| 一本色道久久88综合日韩精品| 亚洲国产精品一区二区三区| 欧美成人精品激情在线观看 | 洋洋av久久久久久久一区| 亚洲精品视频免费| 最近中文字幕mv在线一区二区三区四区| 国产一区二区三区久久| 国产精品色婷婷| 国产日产高清欧美一区二区三区| 国产精品美女主播在线观看纯欲| 欧美亚韩一区| 国产欧美一区二区精品仙草咪 | 久久精品中文字幕一区| 久久久av水蜜桃| 麻豆九一精品爱看视频在线观看免费| 久久不射2019中文字幕| 久久精彩视频| 蜜臀av一级做a爰片久久| 欧美www视频在线观看| 欧美另类一区| 国产精品毛片| 国产亚洲精品bv在线观看| 精品va天堂亚洲国产| 亚洲欧洲视频在线| 一区二区三区久久精品| 午夜精品视频在线观看一区二区 | 亚洲美女在线观看| 亚洲综合欧美日韩| 欧美一区二区播放| 女主播福利一区| 91久久精品国产91性色| 亚洲天天影视| 欧美一站二站| 欧美精品日韩三级| 国产日韩精品在线| 亚洲欧洲日夜超级视频| 蜜臀av性久久久久蜜臀aⅴ四虎| 欧美精品免费在线观看| 国产精品人人做人人爽人人添| 国产一区二区成人| 99精品视频免费在线观看| 欧美有码在线视频| 亚洲高清不卡在线观看| 亚洲一区二区精品在线观看| 麻豆精品在线视频| 国产精品一区二区三区免费观看| 亚洲成色www8888| 亚洲欧美国产高清va在线播| 欧美国产日韩二区| 亚洲专区免费| 欧美日韩精品一区二区天天拍小说| 国产一区二区电影在线观看| 在线亚洲高清视频| 久久一区二区精品| 亚洲一区二区精品在线| 欧美高清hd18日本| 激情另类综合| 欧美在线观看www| 亚洲免费久久| 欧美**字幕| 曰韩精品一区二区| 久久不射2019中文字幕| 日韩午夜免费| 欧美激情网站在线观看| 亚洲福利视频一区| 猫咪成人在线观看| 欧美在线精品免播放器视频| 国产精品黄页免费高清在线观看|