[BZOJ3262]陌上花开 三维偏序 CDQ分治+树状数组 模板

cdq分治似乎是一种特殊的分治，一般的分治中[l,mid]与[mid+1,r]是基本上没有关系的，然而cdq分治中[l,mid]中可能会对[mid+1,r]的答案造成影响。我们可以运用排序、数据结构或者cdq来进行降维操作。

cdq分治的框架(下文代码转自Dirge的博客)：

void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,m);
    cdq(m+1,r);
    //统计[l,mid]对[mid+1, r]的贡献。整体排序后统计。
    sort(pp+l,pp+r+1);
    for(int i = l; i <= r; i++)
        if(pp[i].x <= m)
            add(pp[i].z, 1);
        else
            ans[ pp[i].n ] += sum(pp[i].z);
    for(int i = l; i <= r; i++)
        if(pp[i].x <= m)
            add(pp[i].z, -1);
}

那么bzoj3262就简单啦

#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct flower{
    int x,y,z,cnt,ans;
}d[maxn];
bool tmp(flower a,flower b) {return a.x==b.x?((a.y==b.y)?a.z<b.z:a.y<b.y):a.x<b.x;}
bool cmp(flower a,flower b) {return a.y==b.y?((a.z==b.z)?a.x<b.x:a.z<b.z):a.y<b.y;}
int tree[maxn],k,n,tot,num[maxn];
void add(int pos,int num){for(int i=pos;i<=k;i+=i&-i) tree[i]+=num;}
int query(int pos){int res=0;for(int i=pos;i;i-=i&-i) res+=tree[i];return res;}
void cdq(int l,int r)
{
    if(l==r){
        d[l].ans+=d[l].cnt-1;
        return;
    }
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    sort(d+l,d+mid+1,cmp);
    sort(d+mid+1,d+r+1,cmp);
    int j=l;
    for(int i=mid+1;i<=r;++i){
        for(;j<=mid&&d[j].y<=d[i].y;++j)
            add(d[j].z,d[j].cnt);
        d[i].ans+=query(d[i].z);
    }
    for(int i=l;i<j;++i) add(d[i].z,-d[i].cnt);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) {scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z);d[i].ans=1;}
    sort(d+1,d+n+1,tmp);
    for(int i=1;i<=n;++i)
        if(i!=1&&d[i].x==d[i-1].x&&d[i].y==d[i-1].y&&d[i].z==d[i-1].z) d[tot].cnt++;
        else {d[++tot]=d[i];d[tot].cnt=1;}
    cdq(1,tot);
    sort(d+1,d+tot+1,tmp);
    for(int i=1;i<=tot;++i) num[d[i].ans]+=d[i].cnt;
    for(int i=1;i<=n;++i) printf("%d\n",num[i]);
    return 0;
}