xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

struct  Node{
    
int  l,r;
    
int  cover;
};
struct  arr{
    
int  x,y,z;
};
Node tree[
100000 ];
int  color[ 10001 ];
int  l;
arr p[
21000 ];
arr a[
10100 ];
arr b[
10100 ];
int  ans;
int  cmp( const   void *  no1, const   void *  no2){
    arr 
* nox = (arr * )no1, * noy = (arr * )no2;
    
return  nox -> x - noy -> x;
}
void  build( int  Num, int  l, int  r){
    tree[Num].l
= l;
    tree[Num].r
= r;
    tree[Num].cover
= 0 ;
    
if (l < r){
        
int  mid = (l + r) >> 1 ;
        build(Num
* 2 ,l,mid);
        build(Num
* 2 + 1 ,mid + 1 ,r);
    }
}
void  insert( int  Num, int  l, int  r, int  col){
    
if (l == tree[Num].l && r == tree[Num].r || tree[Num].cover == col){
        tree[Num].cover
= col;
        
return ;
    }
    
if (tree[Num].cover > 0 ){
        tree[Num
* 2 ].cover = tree[Num].cover;
        tree[Num
* 2 + 1 ].cover = tree[Num].cover;
    }
    tree[Num].cover
=- 1 ;
    
int  mid = (tree[Num].l + tree[Num].r) >> 1 ;
    
if (r <= mid) insert(Num * 2 ,l,r,col);
    
else   if (l > mid) insert(Num * 2 + 1 ,l,r,col);
    
else {
        insert(Num
* 2 ,l,mid,col);
        insert(Num
* 2 + 1 ,mid + 1 ,r,col);
    }
}
void  query( int  Num, int  l, int  r){
    
if (tree[Num].cover > 0 ){
        
if ( ! color[tree[Num].cover]){
            color[tree[Num].cover]
= 1 ;
            ans
++ ;
        }
        
return ;
    }
    
else {
        
int  mid = (l + r) >> 1 ;
        query(Num
* 2 ,l,mid);
        query(Num
* 2 + 1 ,mid + 1 ,r);
    }
}
int  main()
{
    
int  t;
    scanf(
" %d " , & t);
    
while (t -- ){
        
int  n;
        scanf(
" %d " , & n);
        l
= 0 ;
        p[l].x
=- 1 ;
        
for ( int  i = 1 ;i <= n; ++ i){
            scanf(
" %d%d " , & a[i].x, & b[i].x);
            l
++ ;
            p[l].x
= a[i].x;
            p[l].y
= i;
            p[l].z
= 0 ;
            l
++ ;
            p[l].x
= b[i].x;
            p[l].y
= i;
            p[l].z
= 1 ;
        }
        qsort(p
+ 1 ,l, sizeof (arr),cmp);
        
int  k = 0 ;
        
for ( int  i = 1 ;i <= l; ++ i){
            
if (p[i].x != p[i - 1 ].x){
                 k
++ ;
                
if ( ! p[i].z){
                    a[p[i].y].y
= k;
                }
                
else  b[p[i].y].y = k;
            }
            
else {
                
if ( ! p[i].z){
                    a[p[i].y].y
= k;
                }
                
else  b[p[i].y].y = k;
            }
        }
        build(
1 , 1 ,k);
        
for ( int  i = 1 ;i <= n; ++ i)
            insert(
1 ,a[i].y,b[i].y,i);
        memset(color,
0 , sizeof (color));
        ans
= 0 ;
        query(
1 , 1 ,k);
        printf(
" %d\n " ,ans);
    }
    
return   0 ;
}




posted on 2009-04-26 20:46 xfstart07 阅读(68) 评论(0)  编辑 收藏 引用 所属分类: 代码库

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