【範例】cdq分治
【題目敘述】https://vjudge.net/problem/HDU-5618
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int x, y, z;
int ans, id;
};
vector <node> v;
int t, 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) return;
int mid = (l+r) >> 1;
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);
}
for (int i = l; i < p; i++){
update(v[i].z, -1);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--){
cin >> n;
v.clear();
for (int i = 0; i < n; i++){
cin >> x >> y >> z;
v.push_back({x, y, z, 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";
}
}
}