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.

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

明显不过的三维偏序问题，cdq分治即可。

我们对x排序之后，cdq分治y，在树状数组上查找z。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=1e5+10;
int T,n,res[N],m=1e5,d[N];
struct node{int x,y,z,id,res;}t[N];
bool operator == (node a,node b){return a.x==b.x&&a.y==b.y&&a.z==b.z;}
int cmpx(node a,node b){return (a.y==b.y&&a.x==b.x)?(a.z<b.z):(a.x==b.x?a.y<b.y:a.x<b.x);}
int cmpy(node a,node b){return a.y==b.y?a.z<b.z:a.y<b.y;}
inline void add(int x,int v){for(;x<=m;x+=lowbit(x)) d[x]+=v;}
inline int ask(int x){int res=0; for(;x;x-=lowbit(x)) res+=d[x]; return res;}
void cdq(int l,int r){
	if(l==r)	return ;	int mid=l+r>>1;
	cdq(l,mid);	cdq(mid+1,r);	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&t[j].y<=t[i].y) add(t[j++].z,1);
		t[i].res+=ask(t[i].z);
	}
	for(int i=l;i<j;i++)	add(t[i].z,-1);
	sort(t+l,t+r+1,cmpy);
}
signed main(){
	cin>>T;
	while(T--){
		scanf("%d",&n); memset(t,0,sizeof t); memset(d,0,sizeof d);
		for(int i=1;i<=n;i++)	scanf("%d %d %d",&t[i].x,&t[i].y,&t[i].z),t[i].id=i;
		sort(t+1,t+1+n,cmpx);	cdq(1,n);
		for(int i=n-1;i>=1;i--)	if(t[i]==t[i+1])	t[i].res=t[i+1].res;
		for(int i=1;i<=n;i++)	res[t[i].id]=t[i].res;
		for(int i=1;i<=n;i++)	printf("%d\n",res[i]);
	}
	return 0;
}