CDQ模板 陌上花开

#include<bits/stdc++.h>
using namespace std;

struct fastio
{
    fastio&operator-(int&a)
    {
        a=0; int n=0; char c=getchar();
        while(c<'0'||c>'9') c=='-'&&(n=1), c=getchar();
        while(c>='0'&&c<='9') a=a*10+(c&15), c=getchar();
        n&&(a=-a); return *this;
    }
}is;
const int N = 200005;
struct BIT
{
    int n, a[N];
    void add(int x, int delta)
    {
        for(;x<=n;x+=x&-x) a[x]+=delta;
    }
    int query(int x)
    {
        int ans = 0;
        for(;x;x-=x&-x) ans += a[x];
        return ans;
    }
}bit;

struct Object
{
    int x,y,z,c,ans;
}a[N];
bool cmpx(const Object&a, const Object&b)
{
    return
    a.x^b.x ?a.x<b.x:
        a.y^b.y ?a.y<b.y:
            a.z<b.z;
}
bool cmpy(const Object&a, const Object&b)
{
    return
        a.y^b.y ?a.y<b.y:
            a.z<b.z;
}

void cdq(int l, int r)
{
    if(l==r) return;
    int mid = l+r>>1;
    cdq(l, mid); cdq(mid+1, r);
    sort(a+l, a+mid+1, cmpy); sort(a+mid+1, a+r+1, cmpy);
    int i=mid+1, j=l;
    for(;i<=r; i++)
    {
        while(a[j].y<=a[i].y && j<=mid) bit.add(a[j].z, a[j].c), j++;
        a[i].ans += bit.query(a[i].z);
    }
    for(int k=l; k<j; k++) bit.add(a[k].z, -a[k].c);
}

int n,k,m;
int cnt[N];
signed main()
{
//  freopen("a.in", "r", stdin);
    is-n-bit.n;
    for(int i=1; i<=n; i++) is-a[i].x-a[i].y-a[i].z;
    
    sort(a+1, a+1+n, cmpx);
    a[1].c = 1; m=1;
    for(int i=2; i<=n; i++)
    {
        if(a[m].x^a[i].x || a[m].y^a[i].y || a[m].z^a[i].z)
            a[++m] = a[i]; //ok to cover
        a[m].c++;
    }
    
    cdq(1, m);
    for(int i=1; i<=m; i++)
        a[i].ans += a[i].c-1;
    for(int i=1; i<=m; i++)
        cnt[a[i].ans] += a[i].c;
    for(int i=0; i<n; i++)
        printf("%d\n", cnt[i]);
}