【CDQ分治】 BZOJ3262 陌上花開

題面在這裡

最經典的三維偏序問題

x用CDQ分治，y排序，z樹狀數組維護

示例程式：

#include<cstdio>
#include<algorithm>
using namespace std;
inline char nc(){
    static char buf[],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}
inline int red(){
    int res=,f=;char ch=nc();
    while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
    while ('0'<=ch&&ch<='9') res=res*+ch-,ch=nc();
    return res*f;
}

const int maxn=;
int n,m=,num[maxn],ans[maxn];
struct data{
    int x,y,z,id;
    inline void read() {x=red();y=red();z=red();}
    inline bool operator==(const data&b)const{return x==b.x&&y==b.y&&z==b.z;}
}a[maxn],t[maxn];
inline const bool cmp(const data&a,const data&b){
    return a.x<b.x || a.x==b.x&&a.y<b.y || a.x==b.x&&a.y==b.y&&a.z<b.z;
}
inline const bool cmpy(const data&a,const data&b){
    return a.y<b.y||a.y==b.y&&a.id<b.id;
}
#define lowbit(x) ((x)&-(x))
int BIT[maxn];
inline void ist(int x,int w){
    for (;x<=m;x+=lowbit(x)) BIT[x]+=w;
}
inline int ask(int x){
    int res=;
    for (;x;x-=lowbit(x)) res+=BIT[x];
    return res;
}
void CDQ(int l,int r){
    if (l==r) return;
    int mid=l+r>>;
    CDQ(l,mid);CDQ(mid+,r);
    for (int i=l;i<=r;i++){
        t[i]=a[i];
        if (i<=mid) t[i].id=;
    }
    sort(t+l,t+r+,cmpy);
    for (int i=l;i<=r;i++)
     if (!t[i].id) ist(t[i].z,);else num[t[i].id]+=ask(t[i].z);
    for (int i=l;i<=r;i++)
     if (!t[i].id) ist(t[i].z,-);
}
int main(){
    n=red();m=red();
    for (int i=;i<=n;i++) a[i].read(),a[i].id=i;
    sort(a+,a++n,cmp);
    for (int i=n-,t=;i;i--){
        if (a[i]==a[i+]) t++;else t=;
        num[a[i].id]=t;
    }
    CDQ(,n);
    for (int i=;i<=n;i++) ans[num[i]]++;
    for (int i=;i<n;i++) printf("%d\n",ans[i]); 
    return ;
}