[BZOJ3262/Luogu3810]陌上花开(CDQ分治,树状数组)

发布于 2018-03-26  65 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3262/Luogu3810]陌上花开(CDQ分治,树状数组)

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Tag

CDQ分治,树状数组

题目大意

求三维偏序。

解决思路

学习三维偏序。对于三维偏序(a,b,c),首先在外面把第一维排序,这样,下面的过程就不需要考虑第一维的影响了。
然后我们二分区间,每一次只考虑左边对右边的贡献,那么因为在外面的时候a已经是有序的了,所以可以保证左边的a一定小于等于右边的a,所以相当于是按照第二维b来进行类似归并排序的操作,对于右边的bi,统计比它小的左边的bj对应的cj有多少不大于ci,那么这个值域的问题可以用树状数组来维护。
需要注意的是,由于有可能有重复的花,所以要先去重。另外,每一次清空树状数组会浪费大量的时间,所以可以用一个时间戳来标记。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lowbit(x) (x)&(-(x))

const int maxN=100010;
const int maxNum=200010;
const int inf=2147483647;

class Data
{
public:
    int a,b,c,ans,cnt;//ans记录总共被贡献了多少答案,cnt记录这一种类的花有多少个
};

int n;
Data D[maxN],Backup[maxN];
int Bit[maxNum];
int histcnt=0,Hist[maxNum];
int Ans[maxN],Cnt[maxN];

bool cmp(Data A,Data B);
void Solve(int l,int r);
void Add(int pos,int key);
int Sum(int pos);

int main()
{
    ios::sync_with_stdio(false);

    int K;
    cin>>n>>K;
    for (int i=1;i<=n;i++){
        cin>>D[i].a>>D[i].b>>D[i].c;
    }
    sort(&D[1],&D[n+1],cmp);//排序
    int p=0;//去重
    for (int i=1,j=0;i<=n;i++)
    {
        j++;
        if ((D[i].a!=D[i+1].a)||(D[i].b!=D[i+1].b)||(D[i].c!=D[i+1].c)){
            D[++p]=D[i];D[p].cnt=j;j=0;
        }
    }

    Solve(1,p);

    for (int i=1;i<=p;i++) Cnt[D[i].ans]+=D[i].cnt;
    for (int i=0;i<n;i++) cout<<Cnt[i]<<endl;
    return 0;
}

bool cmp(Data A,Data B)
{
    if (A.a!=B.a) return A.a<B.a;
    if (A.b!=B.b) return A.b<B.b;
    return A.c<B.c;
}

void Solve(int l,int r)
{
    if (l==r){
        D[l].ans=D[l].cnt-1;
        return;
    }
    int mid=(l+r)>>1;
    Solve(l,mid);Solve(mid+1,r);
    histcnt++;
    int p1=l,p2=mid+1;
    for (int i=l;i<=r;i++)//统计左边对右边的贡献,同时类似归并排序的,将b排序
        if ((p1<=mid)&&((p2>r)||(D[p1].b<=D[p2].b))){
            Backup[i]=D[p1];Add(D[p1].c,D[p1].cnt);p1++;
        }
        else{
            D[p2].ans+=Sum(D[p2].c);Backup[i]=D[p2];p2++;
        }
    for (int i=l;i<=r;i++) D[i]=Backup[i];
    return;
}

void Add(int pos,int key)
{
    while (pos<maxNum)
    {
        if (Hist[pos]!=histcnt) Bit[pos]=key,Hist[pos]=histcnt;//若时间戳不相同,则说明这一次是直接覆盖
        else Bit[pos]+=key;//否则是正常的树状数组的累加
        pos+=lowbit(pos);
    }
    return;
}

int Sum(int pos)
{
    int ret=0;
    while (pos)
    {
        if (Hist[pos]==histcnt) ret+=Bit[pos];//当时间戳与当前时间标记相同时才加进去
        pos-=lowbit(pos);
    }
    return ret;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3262/Luogu3810]陌上花开(CDQ分治,树状数组)


HNCJ OIer 一枚