【BZOJ-3262】陌上花开 CDQ分治（3维偏序）

3262: 陌上花开

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 1439  Solved: 648
[Submit][Status][Discuss]

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

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

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

Source

树套树 CDQ分治

Solution

by CA

和Mokia一样，考虑排序来处理掉一维，然后另一维分治，第三维套上数据结构

首先按s为第一关键字，c、m第二、三关键字排序，然后c维分治，对m维建树状数组。

CDQ(l,r)表示[l,r]中对任意的[l,r]中的x贡献。所以用[l,mid]更新对[mid+1,r]中各元素的贡献。

对c为第一关键字再排序，然后得到[l,mid],[mid+1,r]都是以c维从小到大排序的，把[l,mid]中的x，[mid+1,r]中的y，所有x.c<=y.c的x在他的m上+1，直到x.c>y.c，然后我们Query（y.m）就能得到对y的贡献

统计完还原。

要注意的是：这样有序的分治，我们发现当存在x、y，满足x.s==y.s&&x.c==y.c&&x.m==y.m时，显然排序时靠前的那个，统计答案时会少一个，所以我们需要在分治前去重，额外记录一个个数即可。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define MAXN 100010
#define MAXK 200010
int N,K,tp,rank[MAXN];
struct FlowersNode
{
    int s,c,m,n,id,rk;
    bool operator < (const FlowersNode & A) const
        {
            return s==A.s? (c==A.c? m<A.m:c<A.c):s<A.s; 
        }
}f[MAXN],F[MAXN];
bool cmp(FlowersNode A,FlowersNode B) {return A.c==B.c? A.m<B.m:A.c<B.c;}
namespace BIT
{
    int tree[MAXK];
    inline int lowbit(int x) {return x&-x;}
    inline void Change(int pos,int D) {for (int i=pos; i<=K; i+=lowbit(i)) tree[i]+=D;}
    inline int Query(int pos) {int re=0; for (int i=pos; i; i-=lowbit(i)) re+=tree[i]; return re;}
}
using namespace BIT;
void CDQ(int l,int r)
{
    if (l==r) {F[l].rk+=F[l].n-1; return;}
    int mid=(l+r)>>1;
    CDQ(l,mid); CDQ(mid+1,r);
    sort(F+l,F+mid+1,cmp); sort(F+mid+1,F+r+1,cmp);
//    for (int i=l; i<=r; i++) printf("%d %d %d %d %d
",F[i].s,F[i].c,F[i].m,F[i].rk,F[i].n);
    int pos=l;
    for (int i=mid+1; i<=r; F[i].rk+=Query(F[i].m),i++)
        for (int j=pos; j<=mid && F[j].c<=F[i].c; j++,pos++)
            Change(F[j].m,F[j].n);
    for (int i=l; i<=pos-1; i++) Change(F[i].m,-F[i].n);
    sort(F+l,F+r+1,cmp);     
}
bool compare(FlowersNode A,FlowersNode B) {return (A.s==B.s)&&(A.c==B.c)&&(A.m==B.m);}
int main()
{
    N=read(); K=read();
    for (int i=1; i<=N; i++) f[i].s=read(),f[i].c=read(),f[i].m=read(),f[i].rk=f[i].n=1;
    sort(f+1,f+N+1);
    for (int i=1; i<=N; i++) if (compare(f[i],F[tp])) F[tp].n++; else F[++tp]=f[i];
    CDQ(1,tp);
    for (int i=1; i<=tp; i++) rank[F[i].rk]+=F[i].n;
    for (int i=1; i<=N; i++) printf("%d
",rank[i]);
    return 0;
}