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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久久青草久久久青草|
色综合久久综合网观看|
99久久免费国产精品特黄|
日韩精品久久久肉伦网站
|
久久久一本精品99久久精品66|
亚洲国产精品无码久久久秋霞2|
青青草国产精品久久久久|
欧美精品福利视频一区二区三区久久久精品
|
久久综合狠狠色综合伊人|
亚洲国产成人乱码精品女人久久久不卡
|
久久91精品国产91|
久久精品免费观看|
一本色道久久综合亚洲精品|
国产精品伊人久久伊人电影|
中文字幕乱码人妻无码久久|
开心久久婷婷综合中文字幕|
97久久国产亚洲精品超碰热|
久久天天躁夜夜躁狠狠|
激情久久久久久久久久|
久久精品草草草|
久久99国内精品自在现线|
亚洲国产另类久久久精品|
天堂无码久久综合东京热|
中文字幕亚洲综合久久2|
久久久无码一区二区三区|
久久久噜噜噜久久中文字幕色伊伊
|
天天做夜夜做久久做狠狠|
97精品伊人久久久大香线蕉
|
伊人久久大香线蕉AV一区二区|
一级做a爱片久久毛片|
久久久久免费精品国产|
国产一区二区精品久久|
99久久超碰中文字幕伊人|
久久婷婷五月综合色奶水99啪
|
97精品国产97久久久久久免费|
亚洲国产成人久久一区WWW|
色婷婷综合久久久久中文字幕
|
精品久久久久久成人AV|
久久亚洲精品无码AV红樱桃|
少妇高潮惨叫久久久久久|
无码精品久久久天天影视|