题目：

Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coast and M cities on the West coast (M <= 1000, N <= 1000). K superhighways will be build. Cities on each coast are numbered 1, 2, … from North to South. Each superhighway is straight line and connects city on the East coast with city of the West coast. The funding for the construction is guaranteed by ACM. A major portion of the sum is determined by the number of crossings between superhighways. At most two superhighways cross at one location. Write a program that calculates the number of the crossings between superhighways.

Input

The input file starts with T - the number of test cases. Each test case starts with three numbers – N, M, K. Each of the next K lines contains two numbers – the numbers of cities connected by the superhighway. The first one is the number of the city on the East coast and second one is the number of the city of the West coast.

Output

For each test case write one line on the standard output:
Test case (case number): (number of crossings)

Sample Input

Sample Output

1	Test case 1: 5

解析：

题意：

日本东西海岸分别有M和N个城市，建造K条高速公路连接东西城市，求交点个数。

思路：

如果东海岸x1和西海岸y1之间有连线，x2和y2之间有连线，且$(x_1-x_2)*(y_1-y_2)<0$，那么对应两条公路之间有交点。

以东海岸N个城市为第一关键字，西海岸M个城市为第二关键字进行排序。

那么对第 i 条公路来说，如果前面（i-1)条公路$(x_k,y_k),x_k<x_i,y_k>y_i$,那么这两条公路有交点也就是说在前（i-1）条边中（此时保证$x_k<x_i$)，与第 i 条边相交的边的$y_k$必然大于$y_i$，也就是求$y_i$的逆序数。仍然可以用树状数组解决。

完整代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long 
using namespace std;

const int M = 1003;
LL C[M];
int n, m, k;  //n:东海岸城市数 m:西海岸城市数  k:公路的条数

struct node{
	int x, y;
}edge[1003*1002];

bool cmp(node a, node b){   //a在b的前面返回true
	if(a.x == b.x) return a.y <= b.y;
	else return a.x < b.x;
}

int lowbit(int x){
	return x & (-x);
}

void Modify(int p, int c){  //a[p]增加c以后，调整树状数组C
 	for (int i = p; i <= m; i += lowbit(i)){
 		C[i] += c;
 	}
}

int getsum(int p){
	LL ans = 0;
	for(int i = p; i > 0; i -= lowbit(i)){
		ans += C[i];
	}
	return ans;
}

int main(){
	int T = 0;  //测试用例编号
	int cas;
	scanf("%d", &cas);
	while(cas --){
		scanf("%d %d %d", &n, &m, &k);
		for(int i = 0; i < k; i ++)
			scanf("%d %d", &edge[i].x, &edge[i].y);
		memset(C, 0, sizeof(C));
		sort(edge, edge+k, cmp);
		LL ans = 0;
		for(int i = 0; i < k; i ++){
			Modify(edge[i].y, 1);
			ans += (getsum(m) - getsum(edge[i].y));
		}
		T ++;
		printf("Test case %d: %lld\n", T, ans );
	}
	return 0;
}