陌上花开

题目描述

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

输入格式

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

输出格式

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

分析:

裸的三维偏序,然后我们第一维直接排序,然后对后两维cdq分治,分治的时候我们按照第二维排序然后按顺序把第三维加到BIT里然对于询问,就是求前缀和….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,LL>
#define db double
#define fi first
#define se second
const LL N=2e5+10;
const LL inf=0x3f3f3f3f;
const LL mod=1e9+7;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,k;
namespace BIT
{
    int x[N];
    int lowbit(int now){return now&-now;}
    void change(int now,int v) {for(;now<=k;now+=lowbit(now)) x[now]+=v;}
    int getsum(int now,int ret=1) {for(;now;now-=lowbit(now)) ret+=x[now];return ret;}
}
using namespace BIT;
struct No{int a,b,c;}no[N],no1[N];
int num[N],vis[N],f[N],ans[N],vis2[N],cnt;
bool cmp(int a,int b)
{
    if(no[a].b==no[b].b&&no[a].a==no[b].a) return no[a].c<no[b].c;
    if(no[a].b==no[b].b) return no[a].a<no[b].a;
    return no[a].b<no[b].b;
}
void cdq(int l,int r)
{
    int mid=(l+r)>>1;
    if(l==r) return;
    cdq(l,mid);cdq(mid+1,r);
    for(int i=l;i<=r;i++) num[i]=i;
    sort(num+l,num+r+1,cmp);
    for(int i=l;i<=r;i++)
    {
        int now=num[i];
        if(now<=mid)
            change(no[now].c,vis[now]);
        else if(vis[now])
            f[now]+=getsum(no[now].c)-getsum(0);
    }
    for(int i=l;i<=mid;i++)
        change(no[i].c,-vis[i]);
}
int cmp2(No a,No b)
{
    if(a.a==b.a&&a.b==b.b) return a.c<b.c;
    if(a.a==b.a) return a.b<b.b;
    return a.a<b.a;
}
int main()
{
    memset(x,0,sizeof(x));
    read(n),read(k);
    for(int i=1;i<=n;i++) read(no1[i].a),read(no1[i].b),read(no1[i].c);
    sort(no1+1,no1+n+1,cmp2);
    for(int i=1;i<=n;i++)
    {
        int now=i;vis2[i]=1;
        while(no1[i].a==no1[i+1].a&&no1[i].b==no1[i+1].b&&no1[i].c==no1[i+1].c)
            vis2[now]++,vis2[i+1]=0,i++;
    }
    for(int i=1;i<=n;i++)
        if(vis2[i])
            no[++cnt]=no1[i],vis[cnt]=vis2[i];
//  int sum=0;for(int i=1;i<=cnt;i++) printf("%d %d %d\n",no[i].a,no[i].b,no[i].c),sum+=vis[i];cout<<sum<<endl;return 0;
    cdq(1,cnt);
    for(int i=1;i<=cnt;i++)
        ans[f[i]+vis[i]-1]+=vis[i];
    for(int i=0;i<n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注