• <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久久精品人人做人人爽| 久久久婷婷五月亚洲97号色 | 色婷婷狠狠久久综合五月| 久久w5ww成w人免费| 国产精品久久久久久五月尺| 国产精品美女久久久免费| 精品久久久久久亚洲| 97热久久免费频精品99| 久久精品a亚洲国产v高清不卡| 亚洲精品NV久久久久久久久久| 伊人久久精品线影院| 久久99热只有频精品8| 久久www免费人成看片| 久久精品中文无码资源站| 久久久国产精华液| 亚洲女久久久噜噜噜熟女| 无码精品久久久天天影视| 奇米综合四色77777久久| 2021久久国自产拍精品| 久久久久久免费一区二区三区| 国产成人精品久久| 亚洲嫩草影院久久精品| 久久精品无码一区二区三区免费| 国内精品久久国产| 国产A三级久久精品| 久久天堂电影网| 思思久久99热免费精品6| 亚洲αv久久久噜噜噜噜噜| 久久精品国产亚洲AV无码娇色| 久久久久四虎国产精品| 久久精品成人| 欧美一区二区三区久久综合 | 久久久久久久久66精品片| 久久狠狠爱亚洲综合影院| 亚洲国产精品无码久久久秋霞2| 成人国内精品久久久久一区| 免费精品99久久国产综合精品| 精品国产91久久久久久久a|