陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
程序员文章站
2022-05-14 20:42:58
...
有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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+100;
const int maxk=2e5+100;
struct node{
int a;
int b;
int c;
int id;
}a[maxn],tmp[maxn];
int n,k,cnt,tree[maxk],ans[maxn],res[maxk];
int lowbit(int x)
{
return x&(-x);
}
void update(int tar,int val)
{
for(int i=tar;i<=k;i+=lowbit(i)) tree[i]+=val;
}
int query(int tar)
{
int res=0;
for(int i=tar;i>0;i-=lowbit(i)) res+=tree[i];
return res;
}
bool cmp(node x,node y)
{
if(x.a<y.a) return 1;
if(x.a>y.a) return 0;
if(x.b<y.b) return 1;
if(x.b>y.b) return 0;
if(x.c<y.c) return 1;
return 0;
}
void CDQ(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1,p=l,q=mid+1,cont=l-1;
CDQ(l,mid);CDQ(mid+1,r);
while(p<=mid&&q<=r)
{
if(a[p].b<=a[q].b)
{
update(a[p].c,1);
tmp[++cont]=a[p++];
}
else
{
ans[a[q].id]+=query(a[q].c);
tmp[++cont]=a[q++];
}
}
while(q<=r) ans[a[q].id]+=query(a[q].c),tmp[++cont]=a[q++];
for(int i=l;i<p;i++) update(a[i].c,-1);
while(p<=mid) tmp[++cont]=a[p++];
for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main()
{
cnt=1;
memset(ans,0,sizeof(ans));
memset(res,0,sizeof(res));
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
for(int i=n;i>=1;i--)
{
if(a[i].a==a[i+1].a&&a[i].b==a[i+1].b&&a[i].c==a[i+1].c) ans[a[i].id]+=cnt++;
else cnt=1;
}
CDQ(1,n);
for(int i=1;i<=n;i++) res[ans[i]]++;
for(int i=0;i<n;i++) printf("%d\n",res[i]);
return 0;
}
推荐阅读
-
陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
-
BZOJ 3262: 陌上花开 (cdq分治,三维偏序)
-
bzoj 3262 :陌上花开 (cdq分治 三维偏序)
-
【bzoj3262】陌上花开(cdq分治解决三维偏序问题)一些总结
-
BZOJ - 3262 陌上花开 CDQ分治 三维偏序
-
BZOJ 3262 陌上花开 三维偏序,CDQ分治
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
P3810 -三维偏序(陌上花开)cdq-分治
-
Luogu P3810 【模板】三维偏序(陌上花开) CDQ分治 树状数组
-
CDQ分治--模板 BZOJ 3262--陌上花开【三维偏序】