LOJ3159 NOI2019 弹跳

题意

给你一些平面直角坐标系上的点,每个点向一个矩形连边,让你求点 1 到所有点的最短路

思路

一开始有两个思路,一个是二维线段树,一个是 KD-Tree,但是我的二维线段树做法是三只 \(O(nlog^3n)\) 的, KD-Tree 做法是 \(O(n\sqrt nlogn)\), 然后考场上写了暴力 KD-Tree 建边跑 dij, 然后成功被卡内存成 88 分,之后优化了下空间成功被卡成 96 分,最后看了下 这位巨佬的题解 ,感觉很对,然后写了下,跑的超快,还拿到洛谷最优解

题解

大致思路是建一棵非传统的 KD-Tree, 其中只有叶子是原来的点,其它的节点是虚节点,可以直接滚动分割维度建树,一个点的深度是 \(O(logn)\) 的

然后跑 dij,我们从优先队列中找到这个 dis 最小的矩形,然后在 KD-Tree 上找到被这个矩形覆盖的所有点并更新 dis,如果一个点的子树中没有点需要更新,直接 return,这样一个点只会被更新 dis 一次,因为 dij 的贪心是将 dis 从小到大一个个确定

#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
template<typename T>inline void rd(T&x){int fl=0,ch;while(ch=getchar(),ch<48||57<ch)fl^=!(ch^45);x=(ch&15);while(ch=getchar(),47<ch&&ch<58)x=x*10+(ch&15);if(fl)x=-x;}
template<typename T>inline void pt(T x){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);}
template<typename T>inline void pt(T x,int ch){pt(x),putchar(ch);}
template<typename T>inline T max(const T&x,const T&y){return x<y?y:x;}
template<typename T>inline T min(const T&x,const T&y){return x<y?x:y;}
const int N=70005,INF=0x3f3f3f3f;
int n,m,w,h,rt,nwd,cnt,id[N*2],dis[N*2],vis[N*2];
int nu,nt,xl,xr,yl,yr,nd[N*2],len;
struct data{
    int nt,xl,xr,yl,yr;
    bool operator>(const data&b)const{return nt>b.nt;}
};
std::vector<data>f[N*2];
std::priority_queue<data,std::vector<data>,std::greater<data> >q;
struct po{
    int x[2],id;
    bool operator<(const po&b)const{return x[nwd]^b.x[nwd]?x[nwd]<b.x[nwd]:x[nwd^1]<b.x[nwd^1];}
}p[N];
struct no{
    int mx[2],mn[2],lc,rc,siz;
}t[N*2];
void upd(int u){
    t[u].mn[0]=t[u].mn[1]=INF;
    t[u].mx[0]=t[u].mx[1]=-INF;
    t[u].siz=1;
    int v=t[u].lc;
    if(v){
        t[u].siz+=t[v].siz;
        t[u].mx[0]=max(t[u].mx[0],t[v].mx[0]),t[u].mx[1]=max(t[u].mx[1],t[v].mx[1]);
        t[u].mn[0]=min(t[u].mn[0],t[v].mn[0]),t[u].mn[1]=min(t[u].mn[1],t[v].mn[1]);
    }
    v=t[u].rc;
    if(v){
        t[u].siz+=t[v].siz;
        t[u].mx[0]=max(t[u].mx[0],t[v].mx[0]),t[u].mx[1]=max(t[u].mx[1],t[v].mx[1]);
        t[u].mn[0]=min(t[u].mn[0],t[v].mn[0]),t[u].mn[1]=min(t[u].mn[1],t[v].mn[1]);
    }
}
int bud(int l,int r,int wd){
    int u=++cnt,mid=(l+r)>>1;t[u].siz=1;
    if(l==r){
        id[u]=p[l].id;
        t[u].mn[0]=t[u].mx[0]=p[l].x[0];
        t[u].mn[1]=t[u].mx[1]=p[l].x[1];
        return u;
    }
    bool flag=1;
    for(int i=l+1;i<=r;++i)if(p[i].x[wd]!=p[i-1].x[wd])flag=0;
    if(flag)wd^=1;
    nwd=wd;std::nth_element(p+l,p+mid,p+1+r);
    t[u].lc=bud(l,mid,wd^1);
    t[u].rc=bud(mid+1,r,wd^1);
    upd(u);
    return u;
}
void dfs(int u){
    if(!t[u].siz)return;
    if(t[u].mn[0]>xr||t[u].mx[0]<xl||t[u].mn[1]>yr||t[u].mx[1]<yl)return;
    if(id[u]){
        nd[++len]=id[u];
        t[u].siz=0;
        return;
    }
    dfs(t[u].lc),dfs(t[u].rc);
    t[u].siz=t[t[u].lc].siz+t[t[u].rc].siz;
}
signed main(){
//  freopen("jump.in","r",stdin);
//  freopen("jump.out","w",stdout);
    memset(dis,63,sizeof(dis));
    rd(n),rd(m),rd(w),rd(h);
    rep(i,1,n)rd(p[i].x[0]),rd(p[i].x[1]),p[i].id=i;
    rt=bud(1,n,0);
    rep(i,1,m){
        rd(nu),rd(nt),rd(xl),rd(xr),rd(yl),rd(yr);
        f[nu].push_back((data){nt,xl,xr,yl,yr});
    }
    dis[1]=0;for(int i=0;i<(int)f[1].size();++i)q.push(f[1][i]);vis[1]=1;
    while(!q.empty()){
        nt=q.top().nt,xl=q.top().xl,xr=q.top().xr,yl=q.top().yl,yr=q.top().yr;
        q.pop();len=0;
        dfs(rt);
        for(int i=1;i<=len;++i){
            int u=nd[i];if(vis[u])continue;vis[u]=1;
            dis[u]=nt;
            for(int j=0;j<(int)f[u].size();++j){
                data tp=f[u][j];tp.nt+=nt;
                q.push(tp);
            }
        }
    }
    for(int i=2;i<=n;++i)pt(dis[i],'\n');
    return 0;
}