[BZOJ] 3262: 陌上花开

CDQ分治

大排序降一维，分治降一维，权值树状数组解决一维。

#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=500005;

struct Node{
    int x,y,z;
    int w,f;
    bool operator<(const Node &r)const{
        return (x==r.x&&y==r.y)?z<r.z:(x==r.x)?y<r.y:x<r.x;
    }
}a[MAXN],tmp[MAXN];

int n,m;

int t[MAXN];
inline void update(int x,int w){
    for(;x<=m;x+=x&-x)t[x]+=w;
}
inline int query(int x){
    int ret=0;
    for(;x;x-=x&-x)ret+=t[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);
    int i=l,j=mid+1,p=l;
    while(i<=mid||j<=r){
        if(j>r||(i<=mid&&a[i].y<=a[j].y)) update(a[i].z,a[i].w),tmp[p++]=a[i++];
        else a[j].f+=query(a[j].z),tmp[p++]=a[j++];
    }
    for(i=l;i<=mid;i++) update(a[i].z,-a[i].w);
    for(i=l;i<=r;i++) a[i]=tmp[i];
}

int ans[MAXN];

int main(){
    n=rd();m=rd();
    for(int i=1;i<=n;i++){
        a[i].x=rd();a[i].y=rd();a[i].z=rd();
        a[i].w=1;a[i].f=0;
    }
    sort(a+1,a+1+n);
    int tot=1;
    for(int i=2;i<=n;i++){
        if(a[i].x==a[tot].x&&a[i].y==a[tot].y&&a[i].z==a[tot].z) a[tot].w++;
        else a[++tot]=a[i];
    }
    int sav=n;n=tot;
    cdq(1,tot);
    for(int i=1;i<=n;i++){
        ans[a[i].f+a[i].w]+=a[i].w;
    }
    for(int i=1;i<=sav;i++) printf("%d\n",ans[i]);
    return 0;
}