Jam's problem again
一维快排、二维CDQ、三维树状数组
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100010; 4 5 struct Node{ 6 int x, y, z, id; 7 Node(int x = 0, int y = 0, int z = 0, int id = 0) : 8 x(x), y(y), z(z), id(id) {} 9 bool operator < (const Node &a)const{ 10 if(x != a.x) return x < a.x; 11 if(y != a.y) return y < a.y; 12 return z < a.z; 13 } 14 bool operator == (const Node &a)const{ 15 return x == a.x && y == a.y && z == a.z; 16 } 17 }q[maxn], tq[maxn]; 18 int ans[maxn]; 19 20 bool cmp(Node &a, Node &b){ 21 return a.id < b.id; 22 } 23 24 struct BIT{ 25 int n, c[maxn]; 26 void init(int _n){ 27 n = _n; 28 memset(c, 0, sizeof c); 29 } 30 void add(int i, int v){ 31 for(; i <= n; i += i & -i) c[i] += v; 32 } 33 int sum(int i){ 34 int res = 0; 35 for(; i; i -= i & -i) res += c[i]; 36 return res; 37 } 38 39 }bit; 40 void CDQ(int l, int r){ 41 if(l == r) return; 42 int m = l + r >> 1; 43 CDQ(l, m); CDQ(m + 1, r); 44 int f1 = l, f2 = m + 1; 45 int i = l; 46 while(f1 <= m || f2 <= r){ 47 if(f2 > r || (f1 <= m && q[f1].y <= q[f2].y)){ 48 bit.add(q[f1].z, 1); 49 tq[i++] = q[f1++]; 50 }else{ 51 ans[q[f2].id] += bit.sum(q[f2].z); 52 tq[i++] = q[f2++]; 53 } 54 } 55 for(int i = l; i <= m; i++) bit.add(q[i].z, -1); 56 for(int i = l; i <= r; i++) q[i] = tq[i]; 57 } 58 59 60 int main(){ 61 int t; 62 scanf("%d", &t); 63 while(t--){ 64 int n, maxz = 0; 65 memset(ans, 0, sizeof(ans)); 66 scanf("%d", &n); 67 for(int i = 0; i < n; i++){ 68 scanf("%d %d %d", &q[i].x, &q[i].y, &q[i].z); 69 q[i].id = i; 70 maxz = max(maxz, q[i].z); 71 } 72 bit.init(maxz); 73 sort(q, q + n); 74 for(int i = n - 2; i >= 0; i--){ 75 if(q[i] == q[i + 1]) ans[q[i].id] = ans[q[i + 1].id] + 1; 76 } 77 CDQ(0, n - 1); 78 for(int i = 0; i < n; i++){ 79 printf("%d ", ans[i]); 80 } 81 } 82 }
一维快排、二维CDQ、三维CDQ、（如果有思维就树状数组）
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100010; 4 5 struct Node{ 6 int x, y, z, id; 7 int fg; 8 bool operator < (const Node &a)const{ 9 if(x != a.x) return x < a.x; 10 if(y != a.y) return y < a.y; 11 return z < a.z; 12 } 13 bool operator == (const Node &a)const{ 14 return x == a.x && y == a.y && z == a.z; 15 } 16 }q[maxn], tq1[maxn], tq2[maxn]; 17 int res[maxn]; 18 19 void CDQ2(int l, int r){ 20 if(l == r) return; 21 int m = l + r >> 1; 22 CDQ2(l, m); CDQ2(m + 1, r); 23 int f1 = l, f2 = m + 1, i = l; 24 int cnt = 0; 25 while(f1 <= m || f2 <= r){ 26 if(f2 > r || (f1 <= m && tq1[f1].z <= tq1[f2].z)) { 27 if(tq1[f1].fg == 0) cnt++; 28 tq2[i++] = tq1[f1++]; 29 }else{ 30 if(tq1[f2].fg == 1) res[tq1[f2].id] += cnt; 31 tq2[i++] = tq1[f2++]; 32 } 33 } 34 for(int i = l; i <= r; i++) tq1[i] = tq2[i]; 35 } 36 37 void CDQ1(int l, int r){ 38 if(l == r) return; 39 int m = l + r >> 1; 40 CDQ1(l, m); CDQ1(m + 1, r); 41 int f1 = l, f2 = m + 1, i = l; 42 while(f1 <= m || f2 <= r){ 43 if(f2 > r || (f1 <= m && q[f1].y <= q[f2].y)) { 44 q[f1].fg = 0; 45 tq1[i++] = q[f1++]; 46 }else{ 47 q[f2].fg = 1; 48 tq1[i++] = q[f2++]; 49 } 50 } 51 for(int i = l; i <= r; i++) q[i] = tq1[i]; 52 CDQ2(l, r); 53 } 54 55 int main(){ 56 int t; 57 scanf("%d", &t); 58 while(t--){ 59 int n; 60 memset(res, 0, sizeof res); 61 scanf("%d", &n); 62 for(int i = 0; i < n; i++){ 63 scanf("%d %d %d", &q[i].x, &q[i].y, &q[i].z); 64 q[i].id = i; 65 } 66 sort(q, q + n); 67 for(int i = n - 2; i >= 0; i--){ 68 if(q[i] == q[i + 1]) res[q[i].id] = res[q[i + 1].id] + 1; 69 } 70 CDQ1(0, n - 1); 71 for(int i = 0; i < n; i++) printf("%d ", res[i]); 72 } 73 }