Japan poj3067（树状数组）

Japan
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 36192 Accepted: 9673

Description

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

1
3 4 4
1 4
2 3
3 2
3 1

Sample Output

Test case 1: 5

题目大意：
在一个二部图中分别有顶点数n,m，二部图中两个集合分别用(E,W)表示，现在给出k条边，问你他们的边相交的数量。
思路：
首先思考什么时候会相交：当Ei<Ej 且Wi>Wj，嗯。。。这个稍微画一画就明白了，为了方便我们这样处理，我们可以先对x，y分别降序，然后和Ultra-QuickSort这个题的做法类似，排序完后，第一条边最多有0个交点（一条边肯定没交点对吧），第二条边最多有1个交点，第n条边最多有n-1个交点。现在用每条边最多的交点数减去不是交点的数量，剩下的就是交点数。什么时候不是生交点数？当Ei<Ej,Wi<Wj成立即可，也就是说，只要是第i个点的前面都是不相交点。进行统计就好了，用O(logn)的树状数组维护啥问题没有对吧。
数组开1E6，1E5WA了
代码：

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

const int maxn=1e6+10; 
typedef long long ll;
struct node{
	ll x,y;
}Node[maxn];
ll sum[maxn];
ll n,m,k;
bool cmp(struct node a,struct node b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
void add(ll x,ll v){
	for(;x<=m;x+=(x&-x)){
		sum[x]+=v;
	}
}
ll query(ll x){
	ll s=0;
	for(;x;x-=(x&-x)){
		s+=sum[x];
	}
	return s;
}
int main(){
	ll T;
	scanf("%lld",&T);
	ll ca=1;
	while(T--){
		memset(sum,0,sizeof(sum));
		scanf("%lld%lld%lld",&n,&m,&k);
		for(int i=0;i<k;i++){
			scanf("%lld%lld",&Node[i].x,&Node[i].y);
		}
		sort(Node,Node+k,cmp);//排序是为了方便计算
		ll ans=0;
		for(ll i=0;i<k;i++){
			add(Node[i].y,1);
			ans+=((i+1)-query(Node[i].y));
		}
		printf("Test case %lld: %lld\n",ca++,ans);
	}
}