• <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++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				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 ) //就這里，寫多了一個等號，導致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 ; //不需要訪問到葉節點
            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 巫 閱讀(452) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



97久久天天综合色天天综合色hd|
久久丝袜精品中文字幕|
亚洲中文精品久久久久久不卡|
99久久国产亚洲综合精品|
国产精品美女久久久免费|
91精品国产色综久久|
午夜肉伦伦影院久久精品免费看国产一区二区三区
|
亚洲中文字幕无码久久精品1|
人人狠狠综合久久88成人|
国产免费久久精品99久久|
99久久精品费精品国产|
久久精品国产色蜜蜜麻豆|
深夜久久AAAAA级毛片免费看|
狠狠久久综合伊人不卡|
久久人人爽人人爽人人片av麻烦|
国产人久久人人人人爽|
亚洲国产小视频精品久久久三级|
精品国产一区二区三区久久久狼|
婷婷久久精品国产|
狠狠色噜噜狠狠狠狠狠色综合久久|
少妇无套内谢久久久久|
国产精品久久久天天影视香蕉|
久久亚洲AV成人无码电影|
日产精品久久久久久久|
亚洲人成无码网站久久99热国产|
91久久国产视频|
久久青草国产手机看片福利盒子|
一本久久知道综合久久|
久久久久免费精品国产|
日韩人妻无码一区二区三区久久99|
国产AV影片久久久久久|
99久久www免费人成精品
|
久久精品卫校国产小美女|
久久91精品综合国产首页|
久久99久久成人免费播放|
久久久久免费精品国产|
超级碰久久免费公开视频|
狠狠精品久久久无码中文字幕|
久久久久久久综合综合狠狠|
理论片午午伦夜理片久久|
亚洲国产成人久久综合区|