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

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