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

作者: wjyyy 分类: cdq分治,分治,区间统计,归并,树状数组,解题报告 发布时间: 2018-07-15 22:45

点击量:31

 

   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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */