#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) 编辑 收藏 引用 所属分类:
代码库