陌上花开 CDQ分治

陌上花开

题解:
三维偏序的模板题目。关于三维偏序有很多的写法,之前考试的时候写过树套树,这次采用CDQ。。。CDQ代码短,跑的快。真香。

#include <bits/stdc++.h>

const int MAXN = 500000;

using namespace std;

int n,k,top;
int ans[MAXN],C[MAXN];

struct node{
    int a,b,c,w,f;
    
    friend bool operator < (const node &A,const node &B){
        if(A.a != B.a) return A.a < B.a;
        if(A.b != B.b) return A.b < B.b;
        if(A.c != B.c) return A.c < B.c;
    }

}P[MAXN],T[MAXN];

inline bool cmpA(const node &A,const node &B){
    return A.a < B.a;
}

inline int lowbit(int x){return x & (-x);}

inline int sum(int x){
    int ret = 0;
    for(;x;x -= lowbit(x)) ret += C[x];
    return ret;
}

inline void add(int x,int d){
    for(;x <= k;x += lowbit(x)) C[x] += d;
}

inline void CDQ(int L,int R)
{
    if(L == R) return;
    int M = L + R >> 1;
    CDQ(L,M);CDQ(M+1,R);
    int lc,rc,cnt;
    lc = L;rc = M+1;cnt = L;
    while(lc <= M && rc <= R){
        if(P[lc].b <= P[rc].b){
            add(P[lc].c,P[lc].w);
            T[cnt++] = P[lc++];
        }
        else {
            P[rc].f += sum(P[rc].c);
            T[cnt++] = P[rc++];
        }
    }
    while(lc <= M) {
        add(P[lc].c,P[lc].w);
        T[cnt++] = P[lc++];
    }
    while(rc <= R) {
         P[rc].f += sum(P[rc].c);
        T[cnt++] = P[rc++];
    }
    for(int i = L;i <= M;i++) add(P[i].c,-P[i].w);
    for(int i = L;i <= R;i++) P[i] = T[i];
    
}

int main()
{
    scanf("%d %d",&n,&k);

    for(int i = 1;i <= n;i++) {
        scanf("%d %d %d",&P[i].a,&P[i].b,&P[i].c);
        P[i].w = 1;
    }
    
    sort(P+1,P+n+1);
    top = 1;
    for(int i = 2;i <= n;i++){
        if(P[top].a == P[i].a && P[top].b == P[i].b && P[top].c == P[i].c) P[top].w++;
        else P[++top] = P[i];
    }
    
    CDQ(1,top);
    
    for(int i = 1;i <= top;i++) ans[P[i].f+P[i].w-1] += P[i].w;

    for(int i = 0;i < n;i++) printf("%d\n",ans[i]);

    return 0;
}
Last modification:July 13th, 2019 at 10:02 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment