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

spoiler posted @ 2011年4月11日 19:14 in 树状数组经典题目 , 1309 阅读

题目大意: 顺序给两组平行的点依次编号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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter