题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5126
思路:支持离线,那么我们可以用两次CDQ分治使四维降为二维,降成二维后排个序用树状数组维护下就好了
实现代码:
#include<bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; const int M = 5e5+10; int ans[M],c[M]; struct node { int x,y,z; int kind,id; node(){} node(int x1,int y1,int z1,int k,int i):x(x1),y(y1),z(z1),kind(k),id(i){} }; vector<node>q,q1,q2; vector<int>v; void init(){ q.clear(); v.clear(); memset(c,0,sizeof(c)); } bool cmp(node a,node b){ if(a.x == b.x) return a.id < b.id; return a.x < b.x; } bool cmp1(node a,node b){ if(a.y == b.y) return a.id < b.id; return a.y < b.y; } int lowbit(int x){ return x&-x; } void add(int x,int val){ while(x <= v.size()){ c[x] += val; x += lowbit(x); } } int getsum(int x){ int sum = 0; while(x > 0){ sum += c[x]; x -= lowbit(x); } return sum; } void countstar(){ for(int i = 0;i < q2.size();i ++){ if(q2[i].kind == 0) add(q2[i].z,1); else ans[q2[i].id] += q2[i].kind*getsum(q2[i].z); // cout<<q2[i].id<<" "<<ans[q2[i].id]<<endl; } for(int i = 0;i < q2.size();i ++) if(q2[i].kind == 0) add(q2[i].z,-1); } void cdq1(int l,int r){ if(l >= r) return ; int mid = (l + r) >> 1; cdq1(l,mid); cdq1(mid+1,r); q2.clear(); for(int i = l;i <= mid;i ++) if(q1[i].kind == 0) q2.push_back(q1[i]); for(int i = mid+1;i <= r;i ++) if(q1[i].kind) q2.push_back(q1[i]); sort(q2.begin(),q2.end(),cmp1); countstar(); } void cdq(int l,int r){ if(l >= r) return ; int mid = (l + r) >> 1; cdq(l,mid); cdq(mid+1,r); q1.clear(); for(int i = l;i <= mid;i ++) if(q[i].kind == 0) q1.push_back(q[i]); for(int i = mid+1;i <= r;i ++) if(q[i].kind) q1.push_back(q[i]); sort(q1.begin(),q1.end(),cmp); cdq1(0,q1.size()-1); } int main() { int t,n,op,x,y,z,x1,y1,z1,x2,y2,z2; scanf("%d",&t); while(t--){ scanf("%d",&n); init(); for(int i = 0;i < n;i ++){ scanf("%d",&op); if(op == 1){ scanf("%d%d%d",&x,&y,&z); q.push_back(node(x,y,z,0,i)); v.push_back(z); ans[i] = -1; } else{ scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2); x1--; y1--; z1--; q.push_back(node(x1,y1,z1,-1,i)); q.push_back(node(x2,y2,z2,1,i)); q.push_back(node(x1,y2,z2,-1,i)); q.push_back(node(x2,y1,z2,-1,i)); q.push_back(node(x2,y2,z1,-1,i)); q.push_back(node(x2,y1,z1,1,i)); q.push_back(node(x1,y2,z1,1,i)); q.push_back(node(x1,y1,z2,1,i)); v.push_back(z1); v.push_back(z2); ans[i] = 0; } } //离散化 sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i = 0;i < q.size();i ++) q[i].z = (lower_bound(v.begin(),v.end(),q[i].z)-v.begin())+1; cdq(0,q.size()-1); for(int i = 0;i < n;i ++) if(ans[i] != -1) printf("%d ",ans[i]); } return 0; }