用二维的树状数组做的，但是速度很慢，不知道对不对。
#include <stdio.h>
const int LEN = 1005;
__int64 tree[LEN][LEN]; //记录区间里面的线段数目
void init_t ( int n, int m )
{
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=m; j++ )
tree[i][j] = 0;
}
inline int cupk ( int a )
{
return a&(-a);
}
inline void add ( int n, int m, int i, int j, int num )
{
for ( int ii=i; ii<n; ii+=cupk ( ii ) )
for ( int jj=j; jj<m; jj+=cupk ( jj ) )
tree[ii][jj] += num;
}
inline __int64 ser ( int i, int j )
{
int sum = 0;
for ( int ii=i; ii>=1; ii-=cupk ( ii ) )
for ( int jj=j; jj>=1; jj-=cupk ( jj ) )
sum += tree[ii][jj];
return sum;
}
int main ()
{
int t;
scanf ( "%d", &t );
for ( int c=1; c<t+1; c++ )
{
int n, m, k;
scanf ( "%d%d%d", &n, &m, &k );
init_t ( n, m );
__int64 ans = 0;
for ( int i=0; i<k; i++ )
{
int a, b;
scanf ( "%d%d", &a, &b );
__int64 k = 0;
if ( a>1&&b<m )
k += ser ( a-1, m )-ser ( a-1, b );
if ( a<n&&b>1 )
k += ser ( n, b-1 )-ser ( a, b-1 );
ans += k;
add ( n+1, m+1, a, b, 1 );
}
printf ( "Test case %d: %I64d\n", c, ans );
}
return 0;
}