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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              1#include <cstdio>
              2#include <memory.h>
              3#include <algorithm>
              4using namespace std ;
              5
              6const int MAXN = 41001 ;
              7const int SIZE = 10001 ;
              8
              9struct NODE
             10{
             11    int m_flag ;
             12    int m_start, m_end ;
             13    NODE *leftc , *rightc ;
             14    
             15    void BuildTree(const int& s, const int& e) ;
             16    void Insert(const int& s, const int& e, const int& k) ;
             17    void FindInTree() ;
             18}             ;
             19
             20struct WALL
             21{
             22    int m_pos ;
             23    int m_value ;
             24
             25    bool const operator < ( WALL& b )const
             26    {
             27        if ( m_value < b.m_value )
             28            return true ;
             29        return false ;
             30    }
             31}            wall[SIZE * 2] ;
             32
             33NODE *root ;
             34NODE Stree[MAXN] ;
             35int g_Pos ;
             36int ans , arrSize ;
             37int gFlag[SIZE] ;
             38
             39void NODE::BuildTree(const int& s, const int& e)
             40{
             41    m_flag = 0 ;
             42    m_start = s, m_end = e ;
             43    if ( e == s )
             44    {
             45        leftc = rightc = NULL ;
             46        return ;
             47    }
             48    
             49    int mid = ( s + e ) >> 1 ;
             50    
             51    leftc = &Stree[g_Pos++] ;
             52    rightc = &Stree[g_Pos++] ;
             53    
             54    leftc->BuildTree(s, mid) ;
             55    rightc->BuildTree(mid + 1, e) ;    
             56    
             57}
             58
             59void NODE::Insert(const int& s, const int& e, const int& k)
             60{
             61    if ( m_start == m_end )
             62    {
             63        m_flag = k ;
             64        return ;
             65    }
             66    if ( m_start == s && m_end == e )
             67    {
             68        m_flag = k ;
             69        return ;
             70    }                
             71    if ( m_flag > 0 ){
             72        rightc->m_flag = m_flag ;
             73        leftc->m_flag = m_flag ;
             74        m_flag = -1 ;
             75    }
             76    else if ( m_flag == 0 )
             77        m_flag = k ;
             78    
             79    int mid = ( m_start + m_end ) >> 1 ;
             80    
             81    if ( mid >= e )
             82    {
             83        leftc->Insert( s, e, k ) ;
             84    }
             85    else if ( mid < s ) //就這里，寫多了一個等號，導(dǎo)致WA十幾次
             86    {
             87        rightc->Insert( s, e, k ) ;
             88    }
             89    else {
             90        leftc->Insert( s, mid, k ) ;
             91        rightc->Insert( mid + 1, e, k ) ;
             92    }
             93}
             94
             95void NODE::FindInTree()
             96{
             97    if ( m_flag >= 0  )
             98    {
             99        if ( gFlag[m_flag] == 0 )
            100        {
            101            gFlag[m_flag] = 1 ;
            102            ans++ ;
            103        }
            104        return ; //不需要訪問到葉節(jié)點
            105    }
            106    
            107    if ( m_flag == -1 )
            108    {
            109        leftc->FindInTree() ;
            110        rightc->FindInTree() ;
            111    }
            112    
            113}
            114
            115void Init()
            116{
            117    ans = 0 ;
            118    g_Pos = 1 ;
            119    root = &Stree[0] ;
            120    
            121    root->leftc = root->rightc = NULL ;
            122    memset(gFlag, 0, sizeof(gFlag)) ;
            123}
            124int main()
            125{
            126//     freopen("in.txt", "r", stdin) ;
            127    
            128    int T , n , i , size , x , y ;
            129    int pos[SIZE][2] ;
            130    scanf("%d", &T) ;
            131    
            132    while ( T-- )
            133    {
            134        Init() ;
            135        size = 0 ;
            136        
            137        scanf("%d", &n) ;
            138        
            139        for ( i = 1 ; i <= n ; ++i )
            140        {
            141            scanf("%d %d", &pos[i][0], &pos[i][1]) ;
            142            wall[size].m_pos = i ;
            143            wall[size++].m_value = pos[i][0] ;
            144            wall[size].m_pos = -i ;
            145            wall[size++].m_value = pos[i][1] ;
            146        }
            147        //離散化
            148        sort(wall, wall + size) ;
            149        
            150        x = 1 ;
            151        if ( wall[0].m_pos < 0 )
            152            pos[-wall[0].m_pos][1] = 1 ;
            153        else
            154            pos[wall[0].m_pos][0] = 1 ;
            155        
            156        for ( i = 1 ; i < size ; ++i )
            157        {
            158            if ( wall[i].m_value != wall[i - 1].m_value )
            159            {
            160                x++ ;
            161            }
            162            if ( wall[i].m_pos > 0 )
            163                pos[wall[i].m_pos][0] = x ;
            164            else 
            165                pos[-wall[i].m_pos][1] = x ;
            166            
            167        }
            168        
            169        arrSize = x ;
            170        //線段樹
            171        root->BuildTree( 1, arrSize ) ;
            172        
            173        for ( i = 1 ; i <= n ; ++i )
            174        {
            175            x = pos[i][0] ;
            176            y = pos[i][1] ;
            177            root->Insert( x, y, i ) ;
            178        }
            179        
            180        root->FindInTree() ;
            181 
            182        printf("%d\n", ans) ;
            183    }
            184    return 0 ;
            185}
            186
            187
            188
            189
            

	
            
	
	
            
		posted on 2008-11-16 20:58 巫 閱讀(447) 評論(0)  編輯 收藏 引用  所屬分類: 數(shù)據(jù)結(jié)構(gòu) 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲中文字幕无码久久精品1|
国产精品免费久久久久久久久
|
国内精品久久国产|
国产亚洲精品久久久久秋霞|
久久综合给久久狠狠97色|
亚洲嫩草影院久久精品|
久久久久久久精品成人热色戒|
91性高湖久久久久|
国产精品美女久久福利网站|
国产人久久人人人人爽|
久久人人爽人人爽人人片AV高清|
亚洲精品无码久久一线|
久久久这里有精品|
久久久WWW成人免费毛片|
久久久久久毛片免费播放|
久久午夜福利无码1000合集|
国产成年无码久久久久毛片|
一本一道久久a久久精品综合|
国产精品九九久久精品女同亚洲欧美日韩综合区
|
亚洲欧美伊人久久综合一区二区|
亚洲国产婷婷香蕉久久久久久
|
国产高潮国产高潮久久久91|
久久99九九国产免费看小说|
久久久久久青草大香综合精品|
97久久精品午夜一区二区|
久久青青草原亚洲av无码app|
久久久久久极精品久久久|
成人a毛片久久免费播放|
91精品国产色综合久久|
久久国产精品成人片免费|
久久水蜜桃亚洲av无码精品麻豆|
无码任你躁久久久久久|
久久久久一级精品亚洲国产成人综合AV区
|
久久只这里是精品66|
国产日韩久久免费影院|
91精品日韩人妻无码久久不卡|
久久人与动人物a级毛片|
婷婷久久五月天|
亚洲色大成网站www久久九|
中文国产成人精品久久不卡|
色婷婷综合久久久久中文|