#include
<
iostream
>
using
namespace
std;
struct
arr{
int
x,y;
}a[
1000010
];
int
t;
int
n,m,l;
long
long
MAX;
int
c[
1010
];
int
cmp(
const
void
*
no1,
const
void
*
no2){
arr
*
nox
=
(arr
*
)no1,
*
noy
=
(arr
*
)no2;
if
(nox
->
x
!=
noy
->
x)
return
nox
->
x
-
noy
->
x;
else
return
nox
->
y
-
noy
->
y;
}
int
lowbit(
int
x){
return
x
^
(x
&
(x
-
1
));
}
int
getsum(
int
x){
int
sum
=
0
;
while
(x){
sum
+=
c[x];
x
-=
lowbit(x);
}
return
sum;
}
void
modify(
int
x){
while
(x
<=
m){
c[x]
++
;
x
+=
lowbit(x);
}
}
int
main()
{
scanf(
"
%d
"
,
&
t);
for
(
int
ti
=
1
;ti
<=
t;
++
ti){
scanf(
"
%d%d%d
"
,
&
n,
&
m,
&
l);
for
(
int
i
=
0
;i
<
l;
++
i)
scanf(
"
%d%d
"
,
&
a[i].x,
&
a[i].y);
qsort(a,l,
sizeof
(arr),cmp);
for
(
int
i
=
0
;i
<=
m;
++
i) c[i]
=
0
;
MAX
=
0
;
for
(
int
i
=
0
;i
<
l;
++
i){
MAX
+=
getsum(m)
-
getsum(a[i].y);
modify(a[i].y);
}
printf(
"
Test case %d: %lld\n
"
,ti,MAX);
}
return
0
;
}
posted on 2009-05-29 23:46
xfstart07 阅读(129)
评论(0) 编辑 收藏 引用