BZOJ_3262_陌上花开_CDQ分治+树状数组

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),用三个整数表示。

现在要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。

定义一朵花A比另一朵花B要美丽,当且仅Sa>=Sb,Ca>=Cb,Ma>=Mb。

显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性

Output

包含N行，分别表示评级为0...N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

学习一下CDQ分治。

CDQ分治的思想是分治成两部分，先处理左部分再处理右部分，再考虑左对右的影响。

首先按第一维排序，再把三维都相等的合并。

然后分治，相当于把第二维当成时间，使用归并排序。

归并时如果在左边就把它的第三维加到树状数组里，如果在右边就把答案加上左边的贡献。

最后清一下树状数组。

注意输出时要按照读入的顺序输出。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 100050

struct A {

    int x,y,z,cnt,num;

    bool operator == (const A &u) const {

        return x==u.x&&y==u.y&&z==u.z;

    }

}a[N],v[N],tmp[N];

bool cmp(const A &u,const A &v) {

    if(u.x==v.x&&u.y==v.y) return u.z<v.z;

    if(u.x==v.x) return u.y<v.y;

    return u.x<v.x;

}

int n,c[N*2],maxvalue,ans[N];

void fix(int x,int v) {

    for(;x<=maxvalue;x+=x&(-x)) c[x]+=v;

}

int inq(int x) {

    int re=0;

    for(;x;x-=x&(-x)) re+=c[x];

    return re;

}

void solve(int l,int r) {

    if(l==r) return;

    int mid=(l+r)>>1,i=l,j=mid+1,p=l;

    solve(l,mid); solve(mid+1,r);

    while(i<=mid&&j<=r) {

        if(v[i].y<=v[j].y) fix(v[i].z,v[i].cnt),tmp[p++]=v[i++];

        else tmp[p]=v[j],tmp[p++].num+=inq(v[j++].z);

    }

    while(i<=mid) {

        fix(v[i].z,v[i].cnt); tmp[p++]=v[i++];

    }

    while(j<=r) {

        tmp[p]=v[j],tmp[p++].num+=inq(v[j++].z);

    }

    for(i=l;i<=mid;i++) fix(v[i].z,-v[i].cnt);

    for(i=l;i<=r;i++) v[i]=tmp[i];

}

int main() {

    scanf("%d%d",&n,&maxvalue);

    int i;

    for(i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

    sort(a+1,a+n+1,cmp);

    int tot=0;

    a[0].x=423453;

    for(i=1;i<=n;i++) {

        if(!(a[i]==a[i-1])) v[++tot]=a[i];

        v[tot].cnt++;

    }

    solve(1,tot);

    for(i=1;i<=tot;i++) ans[v[i].num+v[i].cnt]+=v[i].cnt;

    for(i=1;i<=n;i++) printf("%d\n",ans[i]);

}

秒客网