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 1
Ask for the each level of the point.
If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj,
the bigger one level add 1
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)
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 <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h> 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<b.x;
else
{
if(a.y!=b.y)
return a.y<b.y;
else
return a.z<b.z;
}
}
int cmp2(Node a,Node b)
{
return a.id<b.id;
}
void insert(int &node,int l,int r,int tag)
{
if(!node)
node=newnode();
if(l==r)
{
sum[node]++;
return;
}
sum[node]++;
int mid=(l+r)>>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 <iostream>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string.h> 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<b.z;
if(a.x==b.x)
return a.y<b.y;
return a.x<=b.x;
}
int cmp2(Node a,Node b)
{
return a.id<b.id;
}
int lowbit(int x)
{
return x&(-x);
}
void insert(int x,int y)
{
for(int i=x;i<=maxn;i+=lowbit(i))
c[i]+=y;
}
int sum(int x)
{
int s=0;
for(int i=x;i>=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 <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h> 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<b.z;
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int cmp2(Node a,Node b)
{
return a.id<b.id;
}
void fun2(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>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;
}