# 【題解】ZeroJudge c571: 三維偏序問題

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c571
【解題想法】cdq分治

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node{
int x, y, z;
int ans, id;
};
vector <node> v;
int n, x, y, z, bit[100005], ans[100005];

bool cmp1(node a, node b){
if (a.x != b.x) return a.x < b.x;
if (a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
bool cmp2(node a, node b){
if (a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
void update(int x, int d){
while (x < 100005){
bit[x] += d;
x += x & (-x);
}
}
int query(int x){
int ret = 0;
while (x){
ret += bit[x];
x -= x & (-x);
}
return ret;
}
void cdq(int l, int r){
if (l == r || v[l].x == v[r].x) return;
int mid = (l+r)>>1, target = 0;
for (int i = l; i < r; i++){
if (v[i].x != v[i+1].x){
if (abs(i-mid) < abs(target-mid)) target = i;
}
}
mid = target;
cdq(l, mid);
cdq(mid+1, r);
sort(v.begin()+l, v.begin()+mid+1, cmp2);
sort(v.begin()+mid+1, v.begin()+r+1, cmp2);
int p = l;
for (int i = mid+1; i <= r; i++){
while (p <= mid && v[p].y < v[i].y){
update(v[p].z, 1);
p++;
}
v[i].ans += query(v[i].z-1);
}
for (int i = l; i < p; i++){
update(v[i].z, -1);
}
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++){
cin >> x >> y >> z;
v.push_back({n-x+1, n-y+1, n-z+1, 0, i});
}
sort(v.begin(), v.end(), cmp1);
cdq(0, n-1);
for (int i = n-1; i >= 0; i--){
if (i+1 < n && v[i].x == v[i+1].x && v[i].y == v[i+1].y && v[i].z == v[i+1].z){
ans[v[i].id] = ans[v[i+1].id];
}
else ans[v[i].id] = v[i].ans;

}
for (int i = 0; i < n; i++){
cout << ans[i] << "\n";
}
}
```