• <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>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(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)記的, 速度還是可以的, 不過那時對離散化也沒有什么概念, 大
               概是沒怎么接觸, 今天做了這道題目的時候,  也算是明白了 離散化 的基本
               意思,因為 題目的 數(shù)據(jù)范圍很大 , 1- 10000000,直接線段樹的話, 先不說
               內(nèi)存會不會爆, 這么大的范圍估計也是 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://www.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();
                       
            //因為map 已經(jīng)自動排序了,所以直接從 1 --> N 開始標(biāo)記, 離散化 
                       for ( int i = 1;beg != end; ++ beg, ++ i ) {         
                            beg
            ->second = i;  
                       }
                       
            //因為線段樹已經(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é)果跟你手算的一樣么?
            亚洲精品97久久中文字幕无码| 久久精品中文字幕一区| 天天综合久久久网| 久久九色综合九色99伊人| 国产香蕉久久精品综合网| 久久精品中文闷骚内射| 久久九九久精品国产免费直播| 久久热这里只有精品在线观看| 久久精品亚洲一区二区三区浴池 | 99久久精品免费国产大片| 久久中文字幕视频、最近更新| 伊人久久无码中文字幕| 精品国产一区二区三区久久蜜臀| 中文字幕亚洲综合久久菠萝蜜| 国产精品美女久久久久网| 性做久久久久久久久| 亚洲国产精品久久久久| 亚洲国产精品无码久久久蜜芽| 亚洲伊人久久大香线蕉苏妲己| 人妻少妇久久中文字幕| 久久一本综合| 国产激情久久久久影院老熟女免费| 久久人妻AV中文字幕| 伊人久久大香线蕉AV一区二区| 久久综合中文字幕| 久久精品国产亚洲AV高清热| 亚洲日韩欧美一区久久久久我| 91麻豆精品国产91久久久久久| 久久精品国产亚洲AV麻豆网站| 久久久久亚洲国产| 亚洲国产天堂久久综合| 精品国产青草久久久久福利| 久久青青草原国产精品免费| 精品久久无码中文字幕| 久久婷婷五月综合色高清 | 久久99热国产这有精品| 久久精品亚洲中文字幕无码麻豆| 精品久久久中文字幕人妻| 国产成人精品久久| 亚洲AV乱码久久精品蜜桃| 无码国内精品久久人妻蜜桃|