• <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>
            隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
            數據加載中……

            HDU 3458 Rectangles Too!

            題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=3458

            /*
            題意:
                給定n(1<= n <= 100000)個矩形,問最長的遞增矩形序列。矩形A和B
            A = ((xA1 , yA1 ), (xA2 ,yA2 )) 和 B = ((xB1 , yB1 ), (xB2 , yB2 )), 
            如果xA2 < xB1 and yA2 < yB1 則 A <= B,問最長L1 <= L2  <= Ln的長度。

            解法:
            二維線段樹

            思路:
                首先將矩形按左下角x坐標排序,相同的按y坐標排序,接下來就是對于矩形
            A,能否在(xA1 - 1, yA1 - 1)到負無窮之間找到一個先前矩形序列的最大值,如
            果能就將當前矩形接在其后形成新的最大值,這里涉及到了兩個操作,一個是詢問
            ,然后是插入,詢問的是二維區間的最大值,插入的時候是在二維區間的點操作,
            所以很容易想到用二維線段樹來維護每次操作,這題需要注意的是點比較離散,而
            且詢問不是隨意的給出的,而且一開始二維空間是沒有值的,所以不需要預先建樹
            ,事實證明,預先建樹會耗費很大的時間,完全是不必要的。先來談談插入操作,
            我們沒有預先建樹,所以根結點一開始的下標定為-1,這樣在插入的時候如果發現
            根結點的下標為-1,就生成一個新的結點(只需要將計數器賦值給根結點的編號即
            可),然后將根結點的四個兒子全部標記為-1,表示并沒有創建兒子,遞歸四個兒
            子,做同樣的操作,直到只剩一個點的時候。然后是詢問,詢問時如果詢問區間和
            訪問到的結點區間沒有交集自然是直接返回,還有一個剪枝,就是如果當前結點還
            未生成(標記值為-1)說明之前并沒有在以它為根結點的子樹中插入值,也直接返
            回。最后一種情況是當前結點為根的子樹的最大值已經小于等于當前的最大值,也
            直接返回即可。
                二維線段樹的思想類似ZJU 2859 Matrix Searching,只不過一個求的是最大值
            ,一個是最小值。
            */


            #include 
            <iostream>
            #include 
            <algorithm>
            #include 
            <vector>
            using namespace std;

            #define maxn 100010*4

            struct Tree {
                
            int Max;
                
            int son[4];
                
            void clear() {
                    
            int i;
                    
            for(i = 0; i < 4; i++)
                        son[i] 
            = -1;
                    Max 
            = 0;
                }

            }
            T[4*maxn];
            int Tree_Id;

            struct Rectangle {
                
            int x0, x1, y0, y1;
                Rectangle()
            {}
                Rectangle(
            int _x0, int _x1, int _y0, int _y1) {
                    x0 
            = _x0; x1 = _x1;
                    y0 
            = _y0; y1 = _y1;
                }

            }
            ;
            vector 
            < Rectangle > Rec;

            bool cmp(Rectangle a, Rectangle b) {
                
            return a.x0 < b.x0 || (a.x0 == b.x0 && a.y0 < b.y0);
            }


            int Max(int a, int b) {
                
            return a > b ? a : b;
            }

            int Min(int a, int b) {
                
            return a < b ? a : b;
            }


            void Query(int root, int sx, int ex, int sy, int ey, int x0, int x1, int y0, int y1, int& Max) {
                
            if(sx > x1 || ex < x0 || sy > y1 || ey < y0 || root == -1 || T[root].Max <= Max)
                    
            return ;

                
            if(sx <= x0 && x1 <= ex && sy <= y0 && y1 <= ey) {
                    
            if(T[root].Max > Max)
                        Max 
            = T[root].Max;
                    
            return ;
                }


                
            int lmidx = (x0 + x1) >> 1;
                
            int lmidy = (y0 + y1) >> 1;
                
            int rmidx = (lmidx < x1) ? lmidx+1 : lmidx;
                
            int rmidy = (lmidy < y1) ? lmidy+1 : lmidy;

                Query(T[root].son[
            0], sx, ex, sy, ey, x0, lmidx, y0, lmidy, Max);
                Query(T[root].son[
            1], sx, ex, sy, ey, x0, lmidx, rmidy, y1, Max);
                Query(T[root].son[
            2], sx, ex, sy, ey, rmidx, x1, y0, lmidy, Max);
                Query(T[root].son[
            3], sx, ex, sy, ey, rmidx, x1, rmidy, y1, Max);
            }


            void Insert(int& root, int x, int y, int x0, int x1, int y0, int y1, int val) {
                
            if(x < x0 || x > x1 || y < y0 || y > y1)
                    
            return ;

                
            if(root == -1{
                    root 
            = Tree_Id++;
                    T[root].clear();
                }

                
            if(val > T[root].Max)
                    T[root].Max 
            = val;

                
            if(x0 == x && x == x1 && y0 == y && y == y1) {
                    
            return ;
                }

                
                
            int lmidx = (x0 + x1) >> 1;
                
            int lmidy = (y0 + y1) >> 1;
                
            int rmidx = (lmidx < x1) ? lmidx+1 : lmidx;
                
            int rmidy = (lmidy < y1) ? lmidy+1 : lmidy;
                
                Insert(T[root].son[
            0], x, y, x0, lmidx, y0, lmidy, val);
                Insert(T[root].son[
            1], x, y, x0, lmidx, rmidy, y1, val);
                Insert(T[root].son[
            2], x, y, rmidx, x1, y0, lmidy, val);
                Insert(T[root].son[
            3], x, y, rmidx, x1, rmidy, y1, val);
            }

            int n;
            int main() {
                
            int i;
                
            int MaxX, MaxY, MinX, MinY;
                
            while(scanf("%d"&n) != EOF && n) {
                    Rec.clear();
                    MaxX 
            = MaxY = INT_MIN;
                    MinX 
            = MinY = INT_MAX;

                    
            for(i = 0; i < n; i++{
                        
            int x0, x1, y0, y1;
                        scanf(
            "%d %d %d %d"&x0, &y0, &x1, &y1);
                        Rec.push_back(Rectangle(x0, x1, y0, y1));
                        MinX 
            = Min(x0, MinX); MinY = Min(y0, MinY);
                        MaxX 
            = Max(x1, MaxX); MaxY = Max(y1, MaxY);
                    }

                    MinX 
            -= 2; MinY -= 2; MaxX += 2; MaxY += 2;
                    sort(Rec.begin(), Rec.end(), cmp);
                    Tree_Id 
            = 0;
                    
            int ans = 1;
                    
            int root = -1;
                    
            for(i = 0; i < Rec.size(); i++{
                        
            int Max = 0;
                        Query(root, MinX, Rec[i].x0
            -1, MinY, Rec[i].y0-1, MinX, MaxX, MinY, MaxY, Max);
                        Insert(root, Rec[i].x1, Rec[i].y1, MinX, MaxX, MinY, MaxY, Max 
            + 1);
                        
            if(Max + 1 > ans)
                            ans 
            = Max + 1;
                    }

                    printf(
            "%d\n", ans);
                }

                
            return 0;
            }

            posted on 2011-03-30 17:05 英雄哪里出來 閱讀(1169) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹

            久久夜色撩人精品国产| 国产精品久久久久久久| 色综合久久中文色婷婷| 久久久久国色AV免费看图片| 久久亚洲AV无码精品色午夜 | 精品无码久久久久久午夜| 伊人色综合久久天天| 久久精品国产亚洲αv忘忧草 | 久久久久久亚洲精品不卡 | 一本一道久久精品综合| 亚洲精品成人久久久| 久久r热这里有精品视频| 亚洲AV无码成人网站久久精品大| 品成人欧美大片久久国产欧美...| 麻豆成人久久精品二区三区免费 | 99久久精品免费| 亚洲精品乱码久久久久久久久久久久| 青青青国产成人久久111网站| 久久精品国产99国产精品导航| 国产精品美女久久久久AV福利| 伊人久久久AV老熟妇色| 色综合久久无码五十路人妻 | 中文字幕热久久久久久久| 99久久国产亚洲高清观看2024| 久久99久国产麻精品66| 亚洲国产成人精品女人久久久| 四虎国产精品免费久久5151| 蜜臀久久99精品久久久久久小说| 老司机国内精品久久久久| 久久久无码精品亚洲日韩蜜臀浪潮 | 一本一道久久综合狠狠老| 久久亚洲国产精品五月天婷| 久久青草国产手机看片福利盒子| 久久夜色精品国产欧美乱| 狠狠色婷婷久久综合频道日韩 | 中文字幕热久久久久久久| 一本色道久久88综合日韩精品 | 大香伊人久久精品一区二区| 亚洲国产精品嫩草影院久久| 人妻无码久久精品| 伊人久久大香线蕉综合网站|