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

洛谷P3810 【模板】三维偏序(陌上花开)

程序员文章站 2022-05-14 18:41:27
...

题目

题解:

这题我看没有kd树的题解,我就来一发
三维kdO(n5/3)应该是过不了的,我T掉了5个点
我们可以把z排序,xykd树维护,每次计算当前位置前面有多少个xy符合条件(均小于当前位置的xy
但是,这实际上是错误的,当一些z相等时,要查询的范围可能在当前位置之后,于是,我们可以建两棵kd树,分别维护,然后就大功告成了,时间复杂度O(n3/2)

标程:

//T维护在当前位置前,有多少个x和y符合条件
//K维护所有z值相等的点中,有多少个x和y符合条件
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100002;
int n,m,ans,D,i,f[N],k,j,t;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
inline void wri(int a){if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){if(a<0)a=-a,putchar('-');wri(a);puts("");}
inline void Min(int &x,int y){if (y<x) x=y;}
inline void Max(int &x,int y){if (y>x) x=y;}
struct kk{
    int x,y,z;
}a[N];
struct P{
    int l,r,d[2],mn[2],mx[2],v,sum;
    int &operator[](int x){
        return d[x];
    }
    friend bool operator==(P a,P b){
        return a.d[0]==b.d[0] && a.d[1]==b.d[1];
    }
    friend bool operator<(P a,P b){
        return a[D]<b[D];
    }
}p[N];
bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
    return x1<=X1 && X2<=x2 && y1<=Y1 && Y2<=y2;
}
bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
    return X2<x1 || X1>x2 || Y2<y1 || Y1>y2;
}
struct node{
    P now,t[N];
    int rt,cnt;
    void update(int k){
        int l=t[k].l,r=t[k].r;
        for (int i=0;i<2;i++){
            t[k].mn[i]=t[k].mx[i]=t[k][i];
            if (l) Min(t[k].mn[i],t[l].mn[i]),Max(t[k].mx[i],t[l].mx[i]);
            if (r) Min(t[k].mn[i],t[r].mn[i]),Max(t[k].mx[i],t[r].mx[i]);
        }
        t[k].sum=t[k].v+t[l].sum+t[r].sum;
    }
    void ins(int &k,bool D){
        if (!k){
            k=++cnt;
            t[k][0]=t[k].mn[0]=t[k].mx[0]=now[0];
            t[k][1]=t[k].mn[1]=t[k].mx[1]=now[1];
        }
        if (now==t[k]){
            t[k].v+=now.v;t[k].sum+=now.v;
            return;
        }
        if (now[D]<t[k][D]) ins(t[k].l,D^1);
        else ins(t[k].r,D^1);
        update(k);
    }
    int query(int k,int x1,int y1,int x2,int y2){
        if (!k) return 0;
        int tmp=0;
        if (in(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1])) return t[k].sum;
        if (out(x1,y1,x2,y2,t[k].mn[0],t[k].mn[1],t[k].mx[0],t[k].mx[1])) return 0;
        if (in(x1,y1,x2,y2,t[k][0],t[k][1],t[k][0],t[k][1])) tmp+=t[k].v;
        tmp+=query(t[k].l,x1,y1,x2,y2)+query(t[k].r,x1,y1,x2,y2);
        return tmp;
    }
    int build(int l,int r,bool f){
        if (l>r) return 0;
        int mid=l+r>>1;
        D=f;nth_element(p+l,p+mid,p+r+1);
        t[mid]=p[mid];
        t[mid].l=build(l,mid-1,f^1);
        t[mid].r=build(mid+1,r,f^1);
        update(mid);
        return mid;
    }
}T,K;
bool cmp(kk a,kk b){
    return a.z<b.z;
}
int main(){
    n=read();k=read();m=10000;
    for (i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++){
        k=i;
        while (k<n && a[k].z==a[k+1].z) k++;
        for (j=i;j<=k;j++) p[j-i+1][0]=a[j].x,p[j-i+1][1]=a[j].y,p[j-i+1].v=p[j-i+1].sum=1;
        K.rt=K.build(1,k-i+1,0);
        for (j=i;j<=k;j++){
            ans=T.query(T.rt,1,1,a[j].x,a[j].y)+K.query(K.rt,1,1,a[j].x,a[j].y);
            f[ans]++;//把当前位置也算进去了,所以f的输出范围是[1,n]
        }
        for (j=i;j<=k;j++){
            T.now[0]=a[j].x,T.now[1]=a[j].y,T.now.v=T.now.sum=1,T.ins(T.rt,0);
            if (T.cnt==m){
                for (t=1;t<=T.cnt;t++) p[t]=T.t[t];
                T.rt=T.build(1,T.cnt,0);m+=10000;
            }
        }
        i=k;
    }
    for (i=1;i<=n;i++) wln(f[i]);
}