#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 阅读(353)
评论(0) 编辑 收藏 引用 所属分类:
数据结构