【題解】HDU-5618 Jam’s problem again

#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";
        }
    }
}