树状数组求相交公路_POJ3067

传送门：POJ3067

题意：日本岛东海岸与西海岸分别有N和M个城市，现在修高速公路连接东西海岸的城市，求交点个数。

这题也是类似于求逆序对。

做法：记每条告诉公路为(x,y), 即东岸的第x个城市与西岸的第y个城市修一条路。当两条路有交点时，满足（x1-x2）*（y1-y2） < 0。所以，将每条路按x从小到达排序，若x相同，按y从小到大排序。 然后按排序后的公路用树状数组在线更新，求y的逆序数之 和 即为交点个数。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define inff 1LL<<60
#define mem(x)	memset(x,0,sizeof(x))
#define LL long long

#define maxn 1000100
int K,n,m;;
LL c[1100];
struct line
{
	int s,e;
}s[maxn];

bool cmp(line a,line b){
	if(a.s!=b.s)	return a.s<b.s;
	else	return a.e<b.e;
}

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

void update(int x){
	for(;x<=m;c[x]+=1,x+=lowbit(x));
}

int sum(int x){
	int t=0;
	for(;x>0;t+=c[x],x-=lowbit(x));
	return t;
}

int main(int argc, char const *argv[])
{
	int t;
	cin>>t;
	for(int k=1;k<=t;k++){
		LL ans=0;
		mem(c);
		scanf("%d%d%d",&n,&m,&K);
		for (int i = 1; i <= K; ++i)
		{
			scanf("%d%d",&s[i].s,&s[i].e);
		}
		sort(s+1,s+K+1,cmp);
		for(int i=1;i<=K;i++){
			ans+=sum(m)-sum(s[i].e);
			update(s[i].e);
		}
		cout<<"Test case "<<k<<": "<<ans<<endl;
	}
	return 0;
}