zj c571. 三維偏序問題

//zerojudge c571. 三維偏序問題
#pragma GCC optimzize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
//#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef complex<int> P;
#define X real()
#define Y imag()
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e18;
int bit[N];
//bit
void add(int x,int val){
    for(int i=x;i<N;i+=lowbit(i)){
        bit[i]+=val;
    }
}
int query(int x){
    int sum=0;
    for(;x>0;x-=lowbit(x)){
        sum+=bit[x];
    }
    return sum;
}
int ans[N];
struct node{
    int x,y,z;
    int idx;
    bool operator <(const node&o) const{
        if(x!=o.x) return x>o.x;
        //y,z 排序初始必須與要求相反，才能避免算到非嚴格偏序的
        if(y!=o.y) return y<o.y;
        return z<o.z;
    }
}v[N],v2[N];
void CDQ(int l,int r){//[l,r]
    if(l==r) return ;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    int a=l,b=mid+1;
    int st=l;
    stack<pii> undo;
    while(a<=mid||b<=r){
        if(a<=mid&&(b>r||v[a].y>v[b].y)){
            //put a
            add(v[a].z,1);
            undo.push(mp(v[a].z,1));
            v2[st++]=v[a++];
        }
        else{
            //put b
            ans[v[b].idx]+=query(N-1)-query(v[b].z);
            v2[st++]=v[b++];
        }
    }
    //Undo
    while(undo.size()){
        pii now=undo.top();
        undo.pop();
        add(now.F,-now.S);
    }
    //update
    rep(i,l,r){
        v[i]=v2[i];
    }
}
signed main(){
    quick
    int n;
    cin>>n;
    rep(i,1,n){
        cin>>v[i].x>>v[i].y>>v[i].z;
        v[i].idx=i;
    }
    sort(v+1,v+n+1);
    CDQ(1,n);
    rep(i,1,n) cout<<ans[i]<<"\n";
    //ans[i]-> pair's of j that x[i]>x[j],y[i]>y[j],z[i]>z[j]
    return 0;
}