洛谷 P3810/bzoj3262 陌上花开 题解【归并】【树状数组】【cdq分治】

点击量：177

   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

题解：

   如果这个题在二维空间里，那就直接按x排序并求y的顺序对个数。可是三维空间就多限制了一层，也就是在x排序之后，求同时满足y,z的顺序对个数。

   那这时我们不能再对y排序了，但是我们可以比较每个位置的数，在归并排序的过程中，用树状数组求逆序对。归并排序保证了不打乱x的顺序（因为这里归并时的每个区间都是满足单调性的，也就是左区间的x小于右区间），而归并又是为了排y的序，所以我们在这一过程中求出z在两区间中的顺序对个数，那么以z为较大端点的顺序对个数，就是对z的答案。

   同时要记得去重，在题目中提到Sa是可以大于等于Sb的，提前要去重，并给这个点带上权重，也就是相同节点的个数，在做之前处理好自己比自己“美丽”的情况，f[i]=a[i].v-1；求顺序对时如果这个点在左端点，那么计算时就加上这个点的权重。

   在每个归并区间中，树状数组都要清零，这样时间复杂度就变为了$ O(n\log nk)$，不符合题目要求。我们要做的就是在每次归并排序后，对这一区间所做的修改进行逆操作，加过的减去就可以了。要注意归并排序最后如果没有处理加法，返回时也不能处理，清零最好在函数最后，copy数组前完成，就不会产生矛盾。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>

using std::sort;
int lowbit(int x)
{
    return x&(-x);
}
struct node
{
    int x,y,z,v,id;
    node(int x,int y,int z)
    {
        this->x=x;
        this->y=y;
        this->z=z;
        v=1;
    }
    node(){}
    friend bool operator <(node a,node b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        if(a.y!=b.y)
            return a.y<b.y;
        return a.z<b.z;
    }
    friend bool operator >(node a,node b)
    {
        return a.y>b.y;
    }
    friend bool operator ==(node a,node b)
    {
        return a.x==b.x&&a.y==b.y&&a.z==b.z;
    }
}a[101000];
int n,k;
int c[201000];
int ask(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void change(int x,int y)
{
    while(x<=k)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
    return;
}
int f[101000];
node g[101000];
void mergee(int l,int r)
{
    int mid=(l+r>>1);
    if(l==r)
        return;
    mergee(l,mid);
    mergee(mid+1,r);

    int cnt=0,l1=l,l2=mid+1,t=l;
    while(l1<=mid&&l2<=r)
    {
        if(a[l1]>a[l2])
        {
            f[a[l2].id]+=ask(a[l2].z)/*+a[l2].v-1*/;//注释掉的部分只在一开始加一次
            g[t++]=a[l2++];
        }
        else
        {
            change(a[l1].z,a[l1].v);
            g[t++]=a[l1++];
        }
    }
    int tmp=l1;
    while(l1<=mid)
        g[t++]=a[l1++];
    while(l2<=r)
    {
        f[a[l2].id]+=ask(a[l2].z);
        g[t++]=a[l2++];
    }
    for(int i=l;i<tmp;i++)
        change(a[i].z,-a[i].v);
    for(int i=l;i<=r;i++)
        a[i]=g[i];

    return;
}
int d[201000];
node ori[101000];
int main()
{
    memset(c,0,sizeof(c));
    int N;
    scanf("%d%d",&n,&k);
    N=n;
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+1+n);
    int t=1,lst=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[i-1]||i==1)
            continue;
        a[t]=a[i-1];
        a[t].id=t;
        a[t].v=i-lst;
        t++;
        lst=i;
    }
    a[t]=a[n];
    a[t].id=t;
    a[t].v=n+1-lst;
    for(int i=1;i<=t;i++)
    {
        ori[i]=a[i];
        f[i]=a[i].v-1;
    }

    n=t;
    mergee(1,n);
    f[1]=a[1].v-1;
    for(int i=1;i<=n;i++)
        d[f[i]]+=ori[i].v;//这里是调用原来数据，不然会混乱
    for(int i=0;i<N;i++)
        printf("%d\n",d[i]);
    return 0;
}