首页 > 代码库 > acdream1197 Points In Cuboid(hash树状数组)

acdream1197 Points In Cuboid(hash树状数组)

题目链接:http://acdream.info/problem?pid=1197

题意:给出三维空间n个点,m个查询,每次查询某个立方体内的点的个数。

思路:按照一维排序,根据查询插入,其他两位用二位树状数组维护。由于这个坐标太大,二位数组开不出来。这时候就是hash,对于一个位置(x,y),哈希成一个数,作为下标。查询的时候不存在的数字为0.

const int mod=4000007;const int INF=1000000005;const int N=100005;const int M=20011;struct node{	int x,y,z;};node a[N],b[N][2];int n,m;int ans[N];pii Q[N];int cmp(node a,node b){	return a.z<b.z;}int A[mod];int arr[mod];inline int ha(int x){	int k=x%mod;	int i;	for(i=k;;i++)	{		if(i==mod) i=0;		if(A[i])		{			if(A[i]==x) return i;		}		else		{			A[i]=x;			return i;		}	}}inline int find(int x){	int k=x%mod;	int i;	for(i=k;;i++)	{		if(i==mod) i=0;		if(A[i])		{			if(A[i]==x) return i;		}		else		{			return i;		}	}	return 0;}int que(int x,int y){	if(!x||!y) return 0;	int ans=0;	while(x)	{		int i;		for(i=y;i;i-=i&-i) 		{			ans+=arr[find(x*M+i)];		}		x-=x&-x;	}	return ans;}void add(int x,int y){	while(x<M)	{		int i=y;		while(i<M) arr[ha(x*M+i)]++,i+=i&-i;		x+=x&-x;	}}int cal(int t){	int ans=0;	ans+=que(b[t][1].x,b[t][1].y);	ans-=que(b[t][1].x,b[t][0].y-1);	ans-=que(b[t][0].x-1,b[t][1].y);	ans+=que(b[t][0].x-1,b[t][0].y-1);	return ans;}void cal(){	clr(A,0);	clr(arr,0);	int i;	for(i=1;i<=n;i++)	{		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);		a[i].x+=10005;		a[i].y+=10005;	}	scanf("%d",&m);	int j;	for(i=1;i<=m;i++)	{		for(j=0;j<2;j++)		{			scanf("%d%d%d",&b[i][j].x,&b[i][j].y,&b[i][j].z);			b[i][j].x+=10005;			b[i][j].y+=10005;		}		if(b[i][0].x>b[i][1].x) swap(b[i][0].x,b[i][1].x);		if(b[i][0].y>b[i][1].y) swap(b[i][0].y,b[i][1].y);		if(b[i][0].z>b[i][1].z) swap(b[i][0].z,b[i][1].z);		Q[i*2-1]=MP(b[i][0].z-1,-i);		Q[i*2]=MP(b[i][1].z,i);	}	sort(a+1,a+n+1,cmp);	sort(Q+1,Q+2*m+1);	j=1;	for(i=1;i<=m;i++) ans[i]=0;	for(i=1;i<=n;i++)	{		while(j<=2*m&&Q[j].first<a[i].z)		{			int x=Q[j].second;			if(x>0) ans[x]+=cal(x);			else ans[-x]-=cal(-x);			j++;		}		add(a[i].x,a[i].y);	}			while(j<=2*m)	{		int x=Q[j].second;		if(x>0) ans[x]+=cal(x);		else ans[-x]-=cal(-x);		j++;	}	for(i=1;i<=m;i++) printf("%d\n",ans[i]);}int main(){	int num=0;	while(scanf("%d",&n)!=-1)	{		printf("Case #%d:\n",++num);		cal();	}}

 

acdream1197 Points In Cuboid(hash树状数组)