• <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>
            #include <iostream>
            #include 
            <algorithm>
            #include 
            <math.h>
            using namespace std;
            int n;
            struct CPost
            {
                
            int L,R;
            };
            CPost posters[
            10100];
            int x[20200];
            int hash[10000010];
            struct CNode 
            {
                
            int L,R;
                
            bool bCovered; //本區間是否已經被完全覆蓋 
                CNode * pLeft, * pRight;
            };
            CNode Tree[
            100000];
            int nNodeCount = 0;
            int Mid( CNode * pRoot)
            {
                
            return (pRoot->+ pRoot->R)/2;
            }
            void BuildTree( CNode * pRoot, int L, int R)
            {
                pRoot
            ->= L;
                pRoot
            ->= R;
                pRoot
            ->bCovered = false;
                
            if( L == R )
                    
            return;
                nNodeCount 
            ++;
                pRoot
            ->pLeft = Tree + nNodeCount;
                nNodeCount 
            ++;
                pRoot
            ->pRight = Tree + nNodeCount;
                BuildTree( pRoot
            ->pLeft,L,(L+R)/2);
                BuildTree( pRoot
            ->pRight,(L+R)/2 + 1,R);
            }
            bool Post( CNode  *pRoot, int L, int R)
            {
                
            if( pRoot->bCovered )
                    
            return false;
                
            if( pRoot->== L && pRoot->== R) {
                    pRoot
            ->bCovered = true;
                    
            return true;
                }
                
            bool bResult ;
                
            if( R <= Mid(pRoot) ) 
                    bResult 
            = Post( pRoot->pLeft,L,R);
                
            else if( L >= Mid(pRoot) + 1)
                    bResult 
            = Post( pRoot->pRight,L,R);
                
            else {
                    
            bool b1 = Post(pRoot->pLeft ,L,Mid(pRoot));
                    
            bool b2 = Post( pRoot->pRight,Mid(pRoot) + 1,R);
                    bResult 
            = b1 || b2;
                }
                
            //要更新根節點的覆蓋情況
                if( pRoot->pLeft->bCovered && pRoot->pRight->bCovered )
                    pRoot
            ->bCovered = true;
                
            return bResult;
            }
            int main()
            {
                
            int t;
                
            int i,j,k;
                scanf(
            "%d",&t);
                
            int nCaseNo = 0;
                
            while(t--) {
                    nCaseNo 
            ++;
                    scanf(
            "%d",&n);
                    
            int nCount = 0;
                    
            for( i = 0;i < n;i ++ )  {
                        scanf(
            "%d%d"& posters[i].L,& posters[i].R );

                        x[nCount
            ++= posters[i].L;
                        x[nCount
            ++= posters[i].R;
                    }
                    sort(x,x
            +nCount);
                    nCount 
            = unique(x,x+nCount) - x; //去掉重復元素
                    for( i = 0;i < nCount;i ++ )
                        hash[x[i]] 
            = i;
                    nNodeCount 
            = 0;
                    BuildTree( Tree,
            0,nCount - 1);
                    
            int nSum = 0;
                    
            for( i = n - 1;i >= 0;i -- ) { // 從后往前看板是否看得見
                        if( Post(Tree,hash[posters[i].L],hash[posters[i].R]))
                            nSum 
            ++;
                    }
                    printf(
            "%d\n",nSum);
                }
                
            return 0;
            }
            posted on 2010-07-28 22:45 Vontroy 閱讀(288) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹|樹狀數組POJ
            波多野结衣中文字幕久久| 精品久久人人妻人人做精品| 日本高清无卡码一区二区久久| 欧美亚洲日本久久精品| 一极黄色视频久久网站| 久久国产乱子伦免费精品| 精品无码久久久久久久久久| 2021国产精品久久精品| 国产精品久久久久影院嫩草 | 青青草原综合久久大伊人| 久久午夜伦鲁片免费无码| 99久久精品九九亚洲精品| 久久久久亚洲av综合波多野结衣 | 99久久精品费精品国产| 成人午夜精品无码区久久| 久久夜色精品国产亚洲| 久久亚洲日韩看片无码| 国产精品伊人久久伊人电影| 日产精品久久久一区二区| 亚洲国产成人精品无码久久久久久综合 | 日日狠狠久久偷偷色综合96蜜桃| 久久99精品久久久久久久久久| 亚洲成av人片不卡无码久久| 国产99久久久久久免费看| 久久超碰97人人做人人爱| 99久久做夜夜爱天天做精品| 国产99久久九九精品无码| 久久99国产精品一区二区| 亚洲精品乱码久久久久久按摩| 亚洲v国产v天堂a无码久久| 久久亚洲精品无码播放| 中文字幕一区二区三区久久网站| 69久久精品无码一区二区| 久久久亚洲欧洲日产国码二区| 久久笫一福利免费导航| 久久婷婷色香五月综合激情| 少妇被又大又粗又爽毛片久久黑人| 久久精品无码一区二区app| 久久国产视频99电影| 久久久久亚洲AV成人网人人软件 | 男女久久久国产一区二区三区|