POJ 3067(Japan)树状数组求线的交点

题目大意： 顺序给两组平行的点依次编号1~N和1~M，给定K个线段在两组点之间，求相交(cross)的线段对有多少个，同一个起点或终点不算相交

题目分析：把N从大到小排序，注意：当N相等的时候按M的从大到到小！因为我们计算的时候，求N点构成的交点的个数只需要遍历他前面的点对，因为他前面的点对的N值肯定比他大，所以只要M的值比他小肯定就构成了1个交点，所以转换为计算比当前值小的数的个数！这就是树状数组的真谛！然后如果当N相等的时候时候，如果把M小的放前面，计算他后面那个N值相等的点的时候，前面M比他小错误的加上了1，所以当N相等的时候必须按M从大到小的安放！

源程序+部分注释：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;

long long   c[1010];
const int N=1005;
struct node{
	int   w;
	int v;
}s[1000002];

bool cmp(struct node a,struct node b){
	if(a.w==b.w)
		return a.v>b.v;
	else 
		return a.w>b.w;
}
//关键在排序注意一下！

long long   getsum(int x){
	long long    sum=0;
	while(x){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

int modify(int pos){
	while(pos<=N){
		c[pos]+=1;
		pos+=lowbit(pos);
	}
	return 0;
}

int main(){
	int cas,k,r,m ,i,t;
	scanf("%d",&cas);
	while(cas--){
	        k=1;
		scanf("%d  %d %d ",&r,&m,&t);
		memset(c,0,sizeof(c));
		long long   ans=0;
		for(i=1;i<=t;i++)
			scanf("%d %d",&s[i].w,&s[i].v);
		sort(s+1,s+1+t,cmp);
		for(i=1;i<=t;i++){
			ans+=getsum(s[i].v-1);
			modify(s[i].v);
		}
		printf("Test case %d: %lld \n", k++, ans);
	}
	return 0;
}