学步园

//POJ 3067 Japan 线段树 转化

/*
题意：
有一幅图，左边m个结点，右边n个结点，给出k条边连接左边结点和右边结点
	  求这些边相互交叉的个数，一个点只会有两条边经过

思路：
同样将线段转化成点然后放在二维平面图上，对于两条线段[si,ei],[sj,ej]
满足交叉的条件是si<sj&&ei>ej || si>sj&&ei<ej
两条线段如果同起点或者同终点是不会相交的
所以这样就转化为类似POJ 2352 Stars
不一样的是要同起点和同终点的不能算进去

1、对于同起点，即x相同的，只要在线段树里面多一个a[]数组，记录这个数出现几次，然后查询后扣除就行；
2、对于同终点，即y相同的，由于排序后y相同的连在一起，所以在查询前记录这个结点与上一结点的y是否相同,
   如果形同就++res，表示出现的次数，查询后扣除，如果不同就res=0
3、一个点只会有两条边经过，这句话表明没有重边，discuss里面肯定没看题目是乱说的...

PS:没用__int64会爆
*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 1010
#define M 1000010
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int T,n,m,k;
int sum[N<<2],a[N];
__int64 ans;

struct node{
	int x;
	int y;
}s[M];

int cmp(const void *a,const void *b){
	if((*(node *)b).y != (*(node *)a).y)
		return (*(node *)b).y - (*(node *)a).y;
	return (*(node *)a).x - (*(node *)b).x;
}

void Pushup(int rt){
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void Update(int rt,int l,int r,int x){
	if(l == r){
		++sum[rt];
		++a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) Update(lson,x);
	else		 Update(rson,x);
	Pushup(rt);
}

int Query(int rt,int l,int r,int L,int R){
	if(L <= l && R >= r){
		return sum[rt];
	}
	int mid= (l + r) >> 1;
	int res= 0;
	if(L <= mid) res += Query(lson,L,R);
	if(R > mid ) res += Query(rson,L,R);
	return res;
}

int main(){
	int i,j,res,ca = 1;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d %d",&n,&m,&k);
		memset(sum,0,sizeof(sum));
		memset(a,0,sizeof(a));
		ans = 0;
		res = 0;
		for(i = 1; i <= k; ++i)
			scanf("%d %d",&s[i].x,&s[i].y);
		qsort(s+1,k,sizeof(s[0]),cmp);
		for(i = 1; i <= k; ++i){
			int tmp = s[i].y;
			if(i>1 && s[i].y == s[i-1].y)
				++res;
			else
				res = 0;
			ans += Query(1,1,n,1,s[i].x)-a[s[i].x]-res;
			Update(1,1,n,s[i].x);
		}
		printf("Test case %d: %I64d\n",ca++,ans);
	}
	return 0;
}