Jam's problem again

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 640 Accepted Submission(s): 210

Problem Description

Jam like to solve the problem which on the 3D-axis,given

N(1≤N≤100000) points

(x,y,z)(1≤x,y,z≤100000)

If two point such as

(xi,yi,zi) and

(xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add

Ask for the each level of the point.

Input

The first line is

T(1≤T≤15) means

T Case

For each case

The first line is

N means the number of Point and next there are

N line, each line has

(x,y,z)

Output

Output with N line,each line has one number means the lever of point

Sample Input

      1 4 10 4 7 10 6 6 8 2 5 7 3 10 

Sample Output

      1 1 0 0 

      三维偏序，即要求一个三维的点比这个点的小的点有多少个。 

      如果是一维的我们可以怎么做呢？很简单排个序就可以了。 

      如果是二维的呢，同时要求x1<x2和y1<y2点(x1,y1)比点(x2,y2)小。我们可以想到二维树状数组可以 

      很高效率的解决这个问题，但是数据要是有10万，就开不来二维树状数组了。那么可以降维来做。 

      一维排序，二维用树状数组或者线段树来解决，也可以用CDQ分治来做。 

      例如用树状数组，那么按照x排序之后，在树状数组里插入y,边插入边询问，就可以n*logn的效率得到答案。 

      三维的情况呢，同理，第三维可以继续用树状数组或者线段树，但是用树状数组就相当于一个二维树状数组显然会超内存。 

      所以我们可以用动态线段树，不会超内存。 

      如果了用了CDQ分治，那么可以这样一维排序，二维CDQ分治，三维树状数组 

      也可以一维排序，二维CDQ分治，三维CDQ分治 

      一维排序，二维树状数组，三维线段树 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long int LL;const int maxn=1e5;struct Node{ int x,y,z; int id; int num;}a[maxn+5];int n;int rt[maxn+5];int ls[maxn*50];int rs[maxn*50];int sum[maxn*50];int p;int ans1,ans2;int newnode(){ ls[p]=rs[p]=sum[p]=0; return p++;}int lowbit(int x){ return x&(-x);}int cmp(Node a,Node b){ if(a.x!=b.x) return a.x
            
             >1; if(tag<=mid) insert(ls[node],l,mid,tag); else insert(rs[node],mid+1,r,tag);}int query(int &node,int l,int r,int tag){ if(!node) return 0; if(r<=tag) { return sum[node]; } int mid=(l+r)>>1; if(tag<=mid) return query(ls[node],l,mid,tag); else return sum[ls[node]]+query(rs[node],mid+1,r,tag);}int find(int y,int z){ int res=0; for(int i=y;i>=1;i-=lowbit(i)) { res+=query(rt[i],1,ans2,z); } return res;}void update(int y,int z){ for(int i=y;i<=maxn;i+=lowbit(i)) { insert(rt[i],1,ans2,z); }}void init(int y,int z){ memset(rt,0,sizeof(rt)); for(int i=1;i<=y;i++) { rt[i]=i; ls[i]=rs[i]=sum[i]=0; } p=y+1;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); ans1=0; ans2=0; for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); ans1=max(ans1,a[i].y); ans2=max(ans2,a[i].z); a[i].id=i;a[i].num=0; } sort(a+1,a+n+1,cmp); for(int i=n-1;i>=1;i--) { if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z) a[i].num=a[i+1].num+1; } init(ans1,ans2); for(int i=1;i<=n;i++) { a[i].num+=find(a[i].y,a[i].z); update(a[i].y,a[i].z); } sort(a+1,a+n+1,cmp2); for(int i=1;i<=n;i++) { printf("%d\n",a[i].num); } } return 0;}

一维排序，二维CDQ分治，三维树状数组

include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             using namespace std; typedef long long int LL; const int maxn=1e5; int n; struct Node { int x,y,z; int id; int num; }a[maxn+5],b[maxn+5]; int c[maxn+5]; int cmp(Node a,Node b) { if(a.x==b.x&&a.y==b.y) return a.z
            
             =1;i-=lowbit(i)) s+=c[i]; return s; } void fun(int l,int r) { if(l==r) return; int mid=(l+r)>>1; int j=l; int k=mid+1; fun(l,mid); fun(mid+1,r); for(int i=l;i<=r;i++) { if((a[j].y<=a[k].y||k>r)&&j<=mid) { b[i]=a[j++]; insert(b[i].z,1); } else { b[i]=a[k++]; b[i].num+=sum(b[i].z); } } for(int i=l;i<=r;i++) { if(i<=mid) insert(a[i].z,-1); a[i]=b[i]; } } int main() { int t; scanf("%d",&t); while(t--) { memset(c,0,sizeof(c)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].id=i;a[i].num=0; } sort(a+1,a+n+1,cmp); for(int i=n-1;i>=1;i--) { if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z) a[i].num=a[i+1].num+1; } fun(1,n); sort(a+1,a+n+1,cmp2); for(int i=1;i<=n;i++) { printf("%d\n",a[i].num); } } return 0; }

一维排序，二维CDQ分治，三维CDQ分治

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;typedef long long int LL;const int maxn=1e5;struct Node{ int x,y,z; int id,num; int tag; }a[maxn+5],b[maxn+5],c[maxn+5];int ans[maxn+5];int n;int cmp(Node a,Node b){ if(a.x==b.x&&a.y==b.y) return a.z
            
             >1; fun2(l,mid); fun2(mid+1,r); int j=l; int k=mid+1; int res=0; for(int i=l;i<=r;i++) { if((b[j].z<=b[k].z||k>r)&&j<=mid) { c[i]=b[j++]; if(!c[i].tag) res++; } else { c[i]=b[k++]; if(c[i].tag) c[i].num+=res,ans[c[i].id]+=res; } } for(int i=l;i<=r;i++) b[i]=c[i];}void fun1(int l,int r){ if(l==r) return; int mid=(l+r)>>1; fun1(l,mid); fun1(mid+1,r); int j=l; int k=mid+1; for(int i=l;i<=r;i++) { if((a[j].y<=a[k].y||k>r)&&j<=mid) { b[i]=a[j++]; b[i].tag=0; } else { b[i]=a[k++]; b[i].tag=1; } } for(int i=l;i<=r;i++) a[i]=b[i]; fun2(l,r); }int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].num=0; a[i].tag=0; a[i].id=i; } memset(ans,0,sizeof(ans)); sort(a+1,a+n+1,cmp); for(int i=n-1;i>=1;i--) if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z) a[i].num=a[i+1].num+1,ans[a[i].id]=ans[a[i+1].id]+1; fun1(1,n); sort(a+1,a+n+1,cmp2); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); } return 0;}