Luogu | P3810 陌上花开 | cdq 分治 | 三维偏序

Description

有 $n$ 个元素，第 $i$ 个元素有 $a_i$、$b_i$、$c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 的 $j$ 的数量。

对于 $d \in [0, n)$，求 $f(i) = d$ 的数量。

Input Format

第一行两个整数 $n$、$k$，分别表示元素数量和最大属性值。

之后 $n$ 行，每行三个整数 $a_i$、$b_i$、$c_i$，分别表示三个属性值。

Output Format

输出 $n$ 行，第 $d + 1$ 行表示 $f(i) = d$ 的 $i$ 的数量。

Input Sample

Sample 01

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

Output Sample

Sample 01

3
1
3
0
1
0
1
0
0
1

Data Range

$1≤n≤1\times 10^5$ ，$1≤k≤2\times 10^5$。

Solution

第一维按照 $a$ 直接排序，第二维在 Merge 过程中分治（类似 Mergesort），第三维放进树状数组中查询。当然，也可以 Merge 套 Merge。

需要注意的是，题目中有 $a$，$b$，$c$ 相等的情况，需要将 $a$，$b$，$c$ 进行多关键字排序，若完全相等则合并成一个点。每次加入树状数组中的点需要在退出时删除。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define mid ((L+R)>>1)
#define lowbit(x) (x&(-x))

using std::sort;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct pt{
    int a;
    int b;
    int c;
    int w;
    int id;
    int ans;
    friend bool operator < (pt a,pt b){
        if(a.a==b.a){
            if(a.b==b.b)
                return a.c<b.c;
            return a.b<b.b;
        }
        return a.a<b.a;
    }
}s[100005],t[100005];

int N;
int K;
int ww;
int cnt;

int bit[200005];
int ans_va[100005];

void bitModify(int p,int v){
    while(p<=K){
        bit[p]+=v;
        p+=lowbit(p);
    }
    return;
}

int bitQuery(int p){
    int ret=0;
    while(p){
        ret+=bit[p];
        p-=lowbit(p);
    }
    return ret;
}

int bitQuery(int L,int R){
    return bitQuery(R)-bitQuery(L-1);
}

void merge(int L,int R){
    if(L==R)
        return;
    merge(L,mid);
    merge(mid+1,R);
    int i=L;
    rep(j,mid+1,R){
        while(s[i].b<=s[j].b&&i<=mid){
            bitModify(s[i].c,s[i].w);
            i++;
        }
        s[j].ans+=bitQuery(s[j].c);
    }
    rep(k,L,i-1)
        bitModify(s[k].c,-s[k].w);
    i=L;
    int j=mid+1;
    rep(k,L,R){
        if(i>mid)
            t[k]=s[j++];
        else if(j>R)
            t[k]=s[i++];
        else{
            if(s[i].b==s[j].b){
                if(s[i].c<s[j].c)
                    t[k]=s[i++];
                else
                    t[k]=s[j++];
            }
            else if(s[i].b<s[j].b)
                t[k]=s[i++];
            else
                t[k]=s[j++];
        }
    }
    rep(k,L,R)
        s[k]=t[k];
    return;
}

int main(){
    Read(N);
    Read(K);
    rep(i,1,N){
        s[i].id=i;
        Read(s[i].a);
        Read(s[i].b);
        Read(s[i].c);
    }
    sort(s+1,s+1+N);
    rep(i,1,N){
        ww++;
        if(s[i].a==s[i+1].a&&s[i].b==s[i+1].b&&s[i].c==s[i+1].c)
            continue;
        t[++cnt]=s[i];
        t[cnt].w=ww;
        ww=0;
    }
    rep(i,1,cnt)
        s[i]=t[i];
    merge(1,cnt);
    rep(i,1,cnt)
        ans_va[s[i].ans+s[i].w-1]+=s[i].w;
    rep(i,0,N-1)
        printf("%d\n",ans_va[i]);
    return 0;
}