hdu 5618 Jam's problem again （cdq分治+BIT，三维偏序）
题意:
If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1
问每个point的level是多少。
思路：
cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月10日 星期二 19时53分38秒
4File Name :5618.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n;
36struct point
37{
38 int x,y,z;
39 int id;
40 int cnt,sum;
41 void input( int _id)
42 {
43 scanf("%d %d %d",&x,&y,&z);
44 id=_id;
45 }
46 bool operator < (const point &b)const
47 {
48 if (x!=b.x) return x<b.x;
49 if (y!=b.y) return y<b.y;
50 return z<b.z;
51 }
52 bool operator !=(const point &b)const
53 {
54 return x!=b.x||y!=b.y||z!=b.z;
55 }
56}p[N];
57struct BIT
58{
59 int n,t[N];
60 void init( int _n)
61 {
62 n = _n;
63 ms(t,0);
64 }
65 inline int lowbit(int x){ return x&(-x);}
66 void update( int x,int delta)
67 {
68 for ( int i = x ; i <= n ; i+=lowbit(i)) t[i] +=delta;
69 }
70 int Sum( int x)
71 {
72 int ret = 0 ;
73 for ( int i = x ; i >=1 ; i-=lowbit(i)) ret+=t[i];
74 return ret;
75 }
76}bit;
77bool cmpcdq(point a,point b){return a.y<b.y;}
78bool cmpid(point a,point b){return a.id < b.id;}
79void cdq( int l,int r)
80{
81 if (l==r) return;
82 int mid = (l+r)>>1;
83 cdq(l,mid);
84 cdq(mid+1,r);
85 sort(p+l,p+mid+1,cmpcdq);
86 sort(p+mid+1,p+r+1,cmpcdq);
87 int j = l;
88 for ( int i = mid + 1 ; i <= r ; i++)
89 {
90 for ( ; j <= mid && p[j].y <= p[i].y ; j++) bit.update(p[j].z,p[j].cnt);
91 p[i].sum+=bit.Sum(p[i].z);
92 }
93 for ( int i = l ; i < j ; i++) bit.update(p[i].z,-p[i].cnt);
94}
95int tot;
96int ans[N];
97int id[N]; //记录原id对应到了哪个新id
98int main()
99{
100 #ifndef ONLINE_JUDGE
101 freopen("./in.txt","r",stdin);
102 #endif
103 int T;
104 scanf("%d",&T);
105 while (T--)
106 {
107 tot=0;
108 ms(p,0); //多组数据orz
109 scanf("%d",&n);
110 bit.init(N-1);
111 for ( int i = 1 ; i <= n ; i++) p[i].input(i);
112 int cnt = 0;
113 sort(p+1,p+n+1);
114 for ( int i = 1 ; i <= n ; i++)
115 {
116 cnt++;
117 if (p[i]!=p[i+1])
118 {
119 p[i].cnt = cnt;
120 id[p[i].id]=tot+1;
121 p[++tot]=p[i];
122 p[tot].id = tot;
123 cnt=0;
124 }
125 else
126 {
127 id[p[i].id] = tot+1;
128 }
129
130 }
131 cdq(1,tot);
132 //for ( int i = 1 ; i <= n ; i++) ans[id[p[i].id]] = p[i].sum ;
133 //for ( int i = 1 ; i <= n ; i++) printf("%d\n",ans[i]);
134
135 sort(p+1,p+tot+1,cmpid);
136 for ( int i = 1 ; i <= n ; i++) printf("%d\n",p[id[i]].sum+p[id[i]].cnt-1);
137 }
138 #ifndef ONLINE_JUDGE
139 fclose(stdin);
140 #endif
141 return 0;
142}