陌上花开（CDQ分治）

陌上花开

第二遍写这个题了
题意：若某个元素的三个维度的值都小于等于另外一个元素，则是真的小于等于；给出一些元素，求等级分别为 $0n-1$0 n−1的元素数量；而一个元素的等级被定义为小于等于这个元素的元素数量。

思路：(⊙o⊙)…标准的板子，CDQ分治就是细节多一点

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

struct P{
    int x, y, z, cnt, rank;
    bool operator == (const P &rhs) const {
        return x==rhs.x&&y==rhs.y&&z==rhs.z;
    }
}p[maxn];

bool cmp1(const P &a, const P &b) {
    if(a.x==b.x&&a.y==b.y) return a.z<b.z;
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

bool cmp2(const P &a, const P &b) {
    return a.y<b.y;
}

int t[2*maxn], ans[maxn];
int n, k, tot;

inline void add(int x, int d) { while(x<=k) t[x]+=d, x+=x&-x; }
inline int sum(int x) { int ans=0; while(x) ans+=t[x], x-=x&-x; return ans; }

void solve(int l, int r) {
    if(l==r) {
        p[l].rank+=p[l].cnt-1;
        return;
    }
    int m=(l+r)/2;
    solve(l,m), solve(m+1,r);
    sort(p+l,p+m+1,cmp2), sort(p+m+1,p+r+1,cmp2);
    int j=l;
    for(int i=m+1; i<=r; ++i) {
        while(j<=m&&p[j].y<=p[i].y) add(p[j].z,p[j].cnt), ++j;
        p[i].rank+=sum(p[i].z);
    }
    while(--j>=l) add(p[j].z,-p[j].cnt);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), k=read();
    for(int i=1; i<=n; ++i) {
        scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);
        p[i].cnt=1, p[i].rank=0;
    }
    sort(p+1,p+1+n,cmp1);
    int last=1;
    for(int i=2; i<=n; ++i) {
        if(p[i]==p[last]) p[last].cnt++, p[i].cnt=0;
        else last=i;
    }
    for(int i=1; i<=n; ++i) if(p[i].cnt) p[++tot]=p[i];
    solve(1,tot);
    for(int i=1; i<=tot; ++i) ans[p[i].rank]+=p[i].cnt;
    for(int i=0; i<n; ++i) printf("%d\n", ans[i]);
}