#include  < iostream >
#include 
< algorithm >

using   namespace  std;

#define  N 10010

struct  Node{
    
int  x, y;
    Node( 
int  a =   0 int  b =   0  ):x(a), y(b) {}
};

int   n, idx[N * 2 ], data[N * 2 ], pos;
Node d[N];

int  bfind(  int  v ){
    
int  left =   0 , right =  n *   2 ;
    
while ( left +   1 <  right ){
        
int  m =  (left +  right) >>   1 ;
        
if ( data[m] <  v ) left =  m;
        
else   if ( data[m] >  v ) right =  m;
        
else   return  idx[m];
    }
    
return  idx[left];
}

int  tb[N * 8 ], flag[N];
void  insert(  int  l,  int  r,  int  a,  int  b,  int  rt,  int  c ){
    
if ( l ==  a  &&  r ==  b ){
        tb[rt]
=  c;  return ; }
    
int  m =  (l +  r) >>   1 ;
    
if ( tb[rt] >   0  ){
        tb[rt
<< 1 ] =  tb[rt], tb[(rt << 1 ) + 1 ] =  tb[rt], tb[rt] =   0 ; }
    
if ( b <=  m ) insert( l, m, a, b, rt <<   1 , c );
    
else   if ( a >  m ) insert( m +   1 , r, a, b, (rt << 1 ) +   1 , c );
    
else {
        insert( l, m, a, m, rt
<<   1 , c );
        insert( m
+   1 , r, m +   1 , b, (rt << 1 ) +   1 , c ); }
}
void  calc(  int  l,  int  r,  int  rt ){
    
if ( tb[rt] >   0  ) { flag[ tb[rt] ] =   1 return ; }
    
else {
        
if ( l ==  r )  return ;
        
int  m =  (l +  r) >>   1 ;
        calc( l, m, rt
<<   1  );
        calc( m
+   1 , r, (rt << 1 ) +   1  );
    }
}

int  main(){
    
int  test;
    scanf(
" %d " , & test);
    
while ( test --  ){
        scanf(
" %d " , & n );
        
int  u, v;
        
for int  i =   0 ; i <  n;  ++ i ){
            scanf(
" %d%d " , & u, & v );
            d[i]
=  Node( u, v );
            data[i
<< 1 ] =  u, data[(i << 1 ) + 1 ] =  v;
        }
        sort( data, data
+  n *   2  );
        pos
=   1 ; idx[ 0 ] =   1 ;
        
for int  i =   1 ; i <  n *   2 ++ i )
        
if ( data[i] !=  data[i - 1 ] ) idx[i] =   ++ pos;
        
else   idx[i] =  pos;
        
        memset( tb, 
0 sizeof (tb) ); 
        memset( flag, 
0 sizeof (flag) );
        
for int  i =   0 ; i <  n;  ++ i ){
            u
=  bfind( d[i].x ), v =  bfind( d[i].y );
            insert( 
1 , pos, u, v,  1 , i +   1  );
        }
        calc( 
1 , pos,  1  );
        
int  ans =   0 ;
        
for int  i =   1 ; i <=  n;  ++ i )
        
if ( flag[i] ) ans ++ ;
        printf(
" %d\n " , ans );
    }
    
return   0 ;
}
posted on 2009-07-14 20:19 Darren 阅读(331) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理