• <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 巫 閱讀(448) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



 久久综合九色综合久99|
狠狠色丁香婷综合久久|
久久亚洲色一区二区三区|
久久久久亚洲精品无码网址|
久久精品国产99久久香蕉|
色综合久久88色综合天天 |
国产成人精品三上悠亚久久|
99久久99久久精品免费看蜜桃|
99久久99久久精品国产|
一本久久免费视频|
99re这里只有精品热久久|
久久天天躁狠狠躁夜夜不卡|
日本久久久久亚洲中字幕|
国产精品熟女福利久久AV|
无码人妻久久一区二区三区免费
|
97久久精品午夜一区二区|
国产成人香蕉久久久久|
久久久久99精品成人片直播|
久久国产精品免费一区|
99久久成人国产精品免费|
无码人妻久久一区二区三区蜜桃|
 久久综合狠狠综合久久激情 
|
久久久久久亚洲精品无码|
久久av无码专区亚洲av桃花岛|
国产成人AV综合久久|
精品少妇人妻av无码久久|
狠狠色噜噜色狠狠狠综合久久
|
一本久久a久久精品亚洲|
人妻中文久久久久|
久久精品无码免费不卡|
免费观看久久精彩视频|
久久99国内精品自在现线|
人妻少妇久久中文字幕|
国产精品一区二区久久精品涩爱|
狠狠色伊人久久精品综合网|
一本久久a久久精品综合夜夜|
久久人人爽人人爽人人片AV不
|
久久久久99精品成人片|
久久精品国产99久久丝袜|
久久久久亚洲AV无码专区网站|
国产国产成人久久精品|