• <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++博客 ::
首頁(yè) ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評(píng)論
				::
				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 ) //就這里，寫(xiě)多了一個(gè)等號(hào)，導(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 ; //不需要訪問(wèn)到葉節(jié)點(diǎn)
            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        //線段樹(shù)
            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 巫 閱讀(440) 評(píng)論(0)  編輯 收藏 引用  所屬分類(lèi): 數(shù)據(jù)結(jié)構(gòu) 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲人成网站999久久久综合|
国产福利电影一区二区三区久久久久成人精品综合
|
亚洲乱码中文字幕久久孕妇黑人|
亚洲精品无码专区久久同性男|
97视频久久久|
久久婷婷国产综合精品|
久久99国产综合精品女同|
97精品伊人久久久大香线蕉
|
久久伊人五月丁香狠狠色|
久久精品aⅴ无码中文字字幕重口|
www.久久热|
2021国内久久精品|
91精品国产色综久久|
伊人久久综合成人网|
94久久国产乱子伦精品免费|
久久精品国产99国产精品导航
|
97久久超碰成人精品网站|
久久免费国产精品|
国产精品久久久久久搜索|
一级A毛片免费观看久久精品|
99精品国产在热久久无毒不卡|
武侠古典久久婷婷狼人伊人|
久久99国产精品一区二区|
久久久国产打桩机|
久久青青草原亚洲av无码|
国产美女久久久|
久久综合亚洲欧美成人|
久久人人爽人人爽人人片av麻烦|
欧美一区二区精品久久|
久久久久亚洲av无码专区导航
|
日本免费一区二区久久人人澡|
99久久无色码中文字幕人妻|
亚洲欧美久久久久9999|
久久精品国产福利国产琪琪|
亚洲精品高清久久|
国产精品久久久久影院色|
久久婷婷五月综合色高清|
久久久无码精品亚洲日韩蜜臀浪潮
|
久久精品国产影库免费看|
精品久久久久久久久午夜福利|
久久久久久久亚洲Av无码|