欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ3262 || P3810 陌上花开【CDQ分治】【偏序入门】

程序员文章站 2022-03-03 08:52:59
...

Time Limit: 20 Sec
Memory Limit: 256 MB

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的每级花的数量。


题目分析

讲解在这里

CDQ分治 x 偏序问题

概括起来就是
第一维直接排序,第二维CDQ分治,第三维权值树状数组

直接说明很难懂
看代码注释理解会清楚很多


#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;
#define lowbit(x) ((x)&(-x)) 

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}

const int maxn=200010;
int N,n,k;
struct node{int x,y,z,cnt,ans;}a[maxn],b[maxn]; 
int tree[maxn],ans[maxn];

bool cmp(node a,node b){
    if(a.x!=b.x) return a.x<b.x;
    else if(a.y!=b.y) return a.y<b.y;
    else return a.z<b.z;
}

void add(int x,int v){ for(int i=x;i<=k;i+=lowbit(i))tree[i]+=v;}
int qsum(int x){ int res=0; for(int i=x;i>0;i-=lowbit(i))res+=tree[i]; return res;}

void CDQ(int ll,int rr)
{
    if(ll==rr) return;
    int mid=ll+rr>>1;
    CDQ(ll,mid); CDQ(mid+1,rr);//先递归处理子问题

    int t1=ll,t2=mid+1,p=ll;
    while(t2<=rr)
    {
        while(a[t1].y<=a[t2].y&&t1<=mid) //若左子区间的t1对右子区间产生了贡献
        add(a[t1].z,a[t1].cnt),b[p++]=a[t1++];//就插入权值树状数组
        a[t2].ans+=qsum(a[t2].z); b[p++]=a[t2++];//更新左子区间对右子区间的t2产生的贡献
        //b数组是利用归并同时排序了第二维属性yi
    }
    for(int i=ll;i<t1;++i)//清空树状数组
    add(a[i].z,-a[i].cnt);

    while(t1<=mid) b[p++]=a[t1++];
    while(t2<=rr) b[p++]=a[t2++];
    for(int i=ll;i<=rr;++i) a[i]=b[i];
    //注意在处理第二维yi的时候是以yi为关键字拍的序
    //由于一开始已经按第一维xi排序,左子区间的xi一定小于右子区间的,所以不会有问题
}

int main()
{
    N=read();k=read();
    for(int i=1;i<=N;++i)
    b[i].x=read(),b[i].y=read(),b[i].z=read();

    sort(b+1,b+1+N,cmp); //第一维xi直接排序从而忽略影响
    int num=0;
    for(int i=1;i<=N;++i)//统计完全相同的元素
    {
        num++;
        if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z)
        a[++n]=b[i],a[n].cnt=num,a[n].ans=0,num=0;
        //cnt属性表示有多少个相同的,ans属性记录对i满足三维偏序条件的j数量
    }
    CDQ(1,n);

    for(int i=1;i<=n;++i)
    ans[a[i].ans+a[i].cnt-1]+=a[i].cnt;
    for(int i=0;i<N;++i)
    printf("%d\n",ans[i]);
    return 0;
}

上一篇: Attack

下一篇: 桶排序