首页 > 代码库 > 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树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。