神奇的四维偏序

· · 题解

不论是听说还是看题，都让我们知道这是一道四维偏序问题，许多人的做法都是 CDQ 套 CDQ 的 O(n\log_2^3n) 和 三维 K-D Tree 的 O(n^\frac{5}{3})，如果不是这题数据比较随机，一旦出题人把你卡满，就危险了，反正我不敢用三维 K-D Tree，于是想了一个神奇的时间 O(n^\frac{3}{2})，空间 n\log_2n 的做法。

第一步是大家都要做的，通过将 a 维排序将静态四维偏序转换成动态三维偏序，接下来，将编号按 b 维排序，此处相同的不应去重，而应按编号继续比较；然后，使用树状数组套二维 K-D Tree，先建树，每次得到答案后在树上修改即可：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e4+4,M=1e6+6;
char buf[M+5],*p1,*p2,c;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,M,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x;for(c=gc;c<'!';c=gc);
    for(x=0;c>'!';x=x*10+(48^c),c=gc);
    return x;
}
int lx[M],rx[M],ly[M],ry[M],mx[M],my[M],xa[M],ma[M];
int t[M][2],cnt,nrb,nt,lz[M];
int cnt1,cnt2;
struct Tp{int x,y;}a[N];
char now;
inline bool operator<(const Tp &x,const Tp &y){
    return now?x.x<y.x:x.y<y.y;
}
#define ls t[x][0]
#define rs t[x][1]
#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y
int build(int l,int r){
    int x=++cnt,md=l+r>>1,i;now^=1;
    nth_element(a+l,a+md,a+r+1);
    lx[x]=rx[x]=mx[x]=a[md].x;
    ly[x]=ry[x]=my[x]=a[md].y;
    if(l<md){
        ls=build(l,md-1);Min(lx[x],lx[ls]);
        Min(ly[x],ly[ls]);Max(rx[x],rx[ls]);
        Max(ry[x],ry[ls]);
    }
    if(md<r){
        rs=build(md+1,r);Min(lx[x],lx[rs]);
        Min(ly[x],ly[rs]);Max(rx[x],rx[rs]);
        Max(ry[x],ry[rs]);
    }
    return x;
}
inline bool ck(int x){
    return x&&lx[x]<=mx[0]&&ly[x]<=my[0]&&xa[x]>ma[0];
}
inline bool ck2(int x){
    return x&&lx[x]<=mx[0]&&rx[x]>=mx[0]&&ly[x]<=my[0]&&ry[x]>=my[0];
}
inline void pd(int x){
    Max(ma[x],lz[x]);
    if(ls){Max(lz[ls],lz[x]);Max(xa[ls],lz[ls]);}
    if(rs){Max(lz[rs],lz[x]);Max(xa[rs],lz[rs]);}
    lz[x]=0;
}
void ask(int x){
    if(lz[x])pd(x);
    if(rx[x]<=mx[0]&&ry[x]<=my[0]){
        Max(ma[0],xa[x]);return;
    }if(mx[x]<=mx[0]&&my[x]<=my[0])
        Max(ma[0],ma[x]);
    if(ck(ls))ask(ls);
    if(ck(rs))ask(rs);
}
void cg(int x){
    if(lx[x]==mx[0]&&rx[x]==mx[0]&&ly[x]==my[0]&&ry[x]==my[0]){
        Max(lz[x],ma[0]);Max(xa[x],lz[x]);
    }else{
        if(mx[x]==mx[0]&&my[x]==my[0]){
            Max(ma[x],ma[0]);Max(xa[x],ma[x]);
        }if(ck2(ls)){cg(ls);Max(xa[x],xa[ls]);}
        if(ck2(rs)){cg(rs);Max(xa[x],xa[rs]);}
    }
}
struct kdt{
    int rt;
    inline int qry(int x,int y){
        mx[0]=x,my[0]=y,ma[0]=0;
        if(ck(rt))ask(rt);
        return ma[0];
    }
    inline void add(int x,int y,int d){
        mx[0]=x,my[0]=y,ma[0]=d;
        if(ck2(rt))cg(rt);
    }
}tr[N];
int n,bI[N],rk[N],mt,ans[N];
struct Dat{int a[4];}d[N];
int main(){
    int i,j,x;
    for(n=read(),i=1;i<=n;++i)
        d[bI[i]=i]={{read(),read(),read(),read()}};
    stable_sort(d+1,d+n+1,[&](Dat x,Dat y){
        for(i=0;i<4;++i)
            if(x.a[i]!=y.a[i])return x.a[i]<y.a[i];
        return false;
    });
    stable_sort(bI+1,bI+n+1,[&](int x,int y){
        return d[x].a[1]==d[y].a[1]?x<y:d[x].a[1]<d[y].a[1];
    });
    for(i=1;i<=n;++i)rk[bI[i]]=i;
    for(i=1;i<=n;++i){
        nt=i&-i;
        for(j=1;j<=nt;++j){
            x=bI[i-j+1];
            a[j]={d[x].a[2],d[x].a[3]};
        }
        tr[i].rt=build(1,nt);
    }
    for(i=1;i<=n;++i){
        for(j=rk[i];j;j-=j&-j)
            ans[i]=max(ans[i],tr[j].qry(d[i].a[2],d[i].a[3]));
        ans[0]=max(ans[0],++ans[i]);
        for(j=rk[i];j<=n;j+=j&-j)
            tr[j].add(d[i].a[2],d[i].a[3],ans[i]);
    }
    printf("%d\n",ans[0]);
    return 0;
}

空间复杂度很好理解，为什么时间复杂度是 O(n^\frac{3}{2}) 而不用再加一只 \log？

因为树状数组和 K-D Tree 真的很般配！

设 k=\log_2n，则单次查询最坏时间为 \sum_{i\le k}\sqrt{2^i}\le2\sum_{i<=\frac{k}{2}}2^i\le2^{\frac{k}{2}+2}=O(\sqrt{n})