# hdu 5618 Jam's problem again （cdq分治+BIT，三维偏序）

Posted by 111qqz on Tuesday, October 10, 2017

# 题意:

If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1

# 思路：

cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id

``````/* ***********************************************
Author :111qqz
Created Time :2017年10月10日 星期二 19时53分38秒
File Name :5618.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int n;
struct point
{
int x,y,z;
int id;
int cnt,sum;
void input( int _id)
{
scanf("%d %d %d",&x,&y,&z);
id=_id;
}
bool operator < (const point &b)const
{
if (x!=b.x) return x<b.x;
if (y!=b.y) return y<b.y;
return z<b.z;
}
bool operator !=(const point &b)const
{
return x!=b.x||y!=b.y||z!=b.z;
}
}p[N];
struct BIT
{
int n,t[N];
void init( int _n)
{
n = _n;
ms(t,0);
}
inline int lowbit(int x){ return x&(-x);}
void update( int x,int delta)
{
for ( int i = x ; i <= n ; i+=lowbit(i)) t[i] +=delta;
}
int Sum( int x)
{
int ret = 0 ;
for ( int i = x ; i >=1 ;  i-=lowbit(i)) ret+=t[i];
return ret;
}
}bit;
bool cmpcdq(point a,point b){return a.y<b.y;}
bool cmpid(point a,point b){return a.id < b.id;}
void cdq( int l,int r)
{
if (l==r) return;
int mid = (l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(p+l,p+mid+1,cmpcdq);
sort(p+mid+1,p+r+1,cmpcdq);
int j = l;
for ( int i = mid + 1 ; i <= r ; i++)
{
for ( ; j <= mid && p[j].y <= p[i].y ; j++) bit.update(p[j].z,p[j].cnt);
p[i].sum+=bit.Sum(p[i].z);
}
for ( int i = l ; i < j ; i++) bit.update(p[i].z,-p[i].cnt);
}
int tot;
int ans[N];
int id[N]; //记录原id对应到了哪个新id
int main()
{
#ifndef  ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
int T;
scanf("%d",&T);
while (T--)
{
tot=0;
ms(p,0); //多组数据orz
scanf("%d",&n);
bit.init(N-1);
for ( int i = 1 ; i <= n ; i++) p[i].input(i);
int cnt = 0;
sort(p+1,p+n+1);
for ( int i = 1 ; i <= n ; i++)
{
cnt++;
if (p[i]!=p[i+1])
{
p[i].cnt = cnt;
id[p[i].id]=tot+1;
p[++tot]=p[i];
p[tot].id = tot;
cnt=0;
}
else
{
id[p[i].id] = tot+1;
}

}
cdq(1,tot);
//for ( int i = 1 ; i <= n ; i++)  ans[id[p[i].id]] = p[i].sum ;
//for ( int i = 1 ; i <= n ; i++) printf("%d\n",ans[i]);

sort(p+1,p+tot+1,cmpid);
for ( int i = 1 ; i <= n ; i++) printf("%d\n",p[id[i]].sum+p[id[i]].cnt-1);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````

「真诚赞赏，手留余香」