题解 P5471 【[NOI2019]弹跳】

· · 题解

这道题目：

刚开始看，不是裸题吗？***优化建图随便水。

但是空间限制128MB...

当我准备放弃这道题的时候，我...

发现洛谷上有人问我可不可以不把边建出来？？？

听君一席话胜读十年书我茅塞顿开 ，马上就切了此题

然后，这道题就写了我4个多小时...

这题充分考察了对 dijkstra 算法的理解。

首先我们发现，这个弹跳装置，就是把起点对这个子矩形内的所有点连一条边。

然后跑最短路，就 ok 了。

由于毒瘤出题人卡空间，我们不可以用花式建图方式来切此题。所以我们考虑不建出边。

然后我sb的去想一个log的建图方法了。

如果不建出边，怎么跑最短路？

发现 spfa 已死，不是一个好算法显然不能搞，我们去想 dijkstra 。

每一次找到最短路最小的点增广原图的过程，等价于把所有和这个点相邻的点的最短路和 它到原点的最短路长度+边权 取\min。

什么？发现了什么？敏锐的你想到这一步一定发现，对于一个点，它同过弹跳装置向外连的边的边权都是相同的，而且它本身到原点的最短路长度也是固定的...

所以只需要对整个矩形里所有的点的最短路值 和这个数 取\min 不就好了？

然后 dijkstra 打 vis 标记，每一个节点只能被取出一次...

删除这个节点不就好了？

我想到这里以后，马上就有了思路——原问题等价于一个czx最喜欢的数据结构题：

给定一个矩形，上面有n(n \leq 70000)个点，一开始点权均为\infty。支持以下三个操作：

怎么做呢？

发现可以树套树，当然我一开始没往这想，我想了 KD 树。

我们维护一些节点信息：

flag 表示这个点有没有被删除。

flz 表示这个点子树有多少个节点被删除。

tag 表示懒标记（取\min）

w 表示最小值。

mw 表示子树最小值。

sz 表示有多少个子节点（包括自己）

pushup,pushdown 都不算麻烦，关键是删除操作怎么搞？

我们让这个被删除的节点打上一个标记(\text{flag})，以后 pushup 的时候，如果这个点被打了标记，其权值就是\infty。

如果一个点被删除了，其子树仍有节点，那么其\text{mw}表示的是其子树内部的点权最小值。若其子树全部被删除，其\text{mw}就是\infty。

我们只需要通过判断\text{flz}是否=\text{sz}即可。

还有一个细节，就是打标记的时候，如果这个点被删除了，就不更新其w。如果这个点被删除了而其子树仍有点没被删除，不更新w而更新\text{mw}。如果其子树被删光了，什么都不更新。否则都更新。

我这里没考虑清楚，所以一直8分...

实现细节

注意我们还需要得知这个点的位置。所以需要用 pair 来存\text{w},\text{mw}。

pushup:

inline void pushup(int rt){
    g[rt].flz=g[g[rt].l].flz+g[g[rt].r].flz+g[rt].flag;
    if (g[rt].flag) g[rt].w.first=inf,g[rt].w.second=inf;
    g[rt].mw=g[rt].w;
    chkmin(g[rt].mw,min(g[g[rt].l].mw,g[g[rt].r].mw));
}

pushdown:

inline void pushdown(int rt){
    if (g[rt].tag==inf) return;
    int ls=g[rt].l,rs=g[rt].r;
    if (ls){
        chkmin(g[ls].tag,g[rt].tag);
        if (!g[ls].flag) chkmin(g[ls].w.first,g[rt].tag);
        if (g[ls].sz!=g[ls].flz) chkmin(g[ls].mw.first,g[rt].tag);
    }
    if (rs){
        chkmin(g[rs].tag,g[rt].tag);
        if (!g[rs].flag) chkmin(g[rs].w.first,g[rt].tag);
        if (g[rs].sz!=g[rs].flz) chkmin(g[rs].mw.first,g[rt].tag);
    }
    g[rt].tag=inf;
}

完整代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#ifdef Fading
#define gc getchar
#endif
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
int n,m,T,W,dis[200001],H,D,cnt,L,root,xma,yma,xmi,ymi;//x->0,y->1
#define P pair<int,int>
inline P min(const P &x,const P &y){return (x>y?y:x);}
inline void chkmin(P &x,const P &y){if (x>y) x=y;}
inline void chkmin(int &x,const int &y){if (x>y) x=y;}
inline void chkmax(int &x,const int &y){if (x<y) x=y;}
struct point{
    int x,y,id;
}a[100001];
inline bool cmp(const point &a, const point &b){
    if (D){
        if (a.x!=b.x) return a.x<b.x;
        return (a.y<b.y); 
    }else{
        if (a.y!=b.y) return a.y<b.y;
        return (a.x<b.x); 
    }
}
struct KD{
    int xmin,xmax,ymin,ymax;
    int l,r,x,y,sz,flz;
    P w,mw;
    int flag,tag;
}g[100001];
#define mid ((lb+rb)>>1) 
#define inf (0x3f3f3f3f)
void build(int &rt,int lb,int rb,int det){
    if (lb>rb) return (void)(rt=0);
    rt=++cnt;g[rt].tag=inf;D=det;nth_element(a+lb,a+mid,a+rb+1,cmp);
    g[rt].x=a[mid].x;g[rt].y=a[mid].y;g[rt].w=make_pair(inf,a[mid].id);
    if (a[mid].id==1) g[rt].w.first=0;
    build(g[rt].l,lb,mid-1,det^1);build(g[rt].r,mid+1,rb,det^1);
    int ls=g[rt].l,rs=g[rt].r;g[rt].xmax=g[rt].xmin=g[rt].x;
    g[rt].ymax=g[rt].ymin=g[rt].y,g[rt].mw=g[rt].w;
    if (ls) chkmin(g[rt].xmin,g[ls].xmin),chkmin(g[rt].ymin,g[ls].ymin);
    if (ls) chkmax(g[rt].xmax,g[ls].xmax),chkmax(g[rt].ymax,g[ls].ymax);
    if (rs) chkmin(g[rt].xmin,g[rs].xmin),chkmin(g[rt].ymin,g[rs].ymin);
    if (rs) chkmax(g[rt].xmax,g[rs].xmax),chkmax(g[rt].ymax,g[rs].ymax);
    chkmin(g[rt].mw,min(g[ls].mw,g[rs].mw));
    g[rt].sz=1+g[ls].sz+g[rs].sz;
}
inline bool all_in_it(const KD &rt){
    return (rt.xmax<=xma)&&(rt.xmin>=xmi)&&(rt.ymax<=yma)&&(rt.ymin>=ymi);
}
inline bool in_it(const int &x,const int &y){
    return (x>=xmi&&x<=xma&&y>=ymi&&y<=yma);
}
inline bool pd(const KD &rt){
    return !((rt.xmin>xma)||(rt.xmax<xmi)||(rt.ymin>yma)||(rt.ymax<ymi));
}
inline void pushdown(int rt){
    if (g[rt].tag==inf) return;
    int ls=g[rt].l,rs=g[rt].r;
    if (ls){
        chkmin(g[ls].tag,g[rt].tag);
        if (!g[ls].flag) chkmin(g[ls].w.first,g[rt].tag);
        if (g[ls].sz!=g[ls].flz) chkmin(g[ls].mw.first,g[rt].tag);
    }
    if (rs){
        chkmin(g[rs].tag,g[rt].tag);
        if (!g[rs].flag) chkmin(g[rs].w.first,g[rt].tag);
        if (g[rs].sz!=g[rs].flz) chkmin(g[rs].mw.first,g[rt].tag);
    }
    g[rt].tag=inf;
}
inline void pushup(int rt){
    g[rt].flz=g[g[rt].l].flz+g[g[rt].r].flz+g[rt].flag;
    if (g[rt].flag) g[rt].w.first=inf,g[rt].w.second=inf;
    g[rt].mw=g[rt].w;
    chkmin(g[rt].mw,min(g[g[rt].l].mw,g[g[rt].r].mw));
}
void Update(int rt,int W){
    if (!rt||!pd(g[rt])||g[rt].tag<=W) return;
    if (all_in_it(g[rt])){
        chkmin(g[rt].tag,W);
        if (!g[rt].flag) chkmin(g[rt].w.first,W);
        if (g[rt].sz!=g[rt].flz) chkmin(g[rt].mw.first,W);
        return;
    }
    if (in_it(g[rt].x,g[rt].y)) if (!g[rt].flag) chkmin(g[rt].w.first,W);
    pushdown(rt);Update(g[rt].l,W);Update(g[rt].r,W);pushup(rt);
 }
void Del(int rt,int x,int y,int det){
    if (!rt) return;
    pushdown(rt);D=det;
    if (g[rt].x==x&&g[rt].y==y) return (void)(g[rt].flag=1,pushup(rt)); 
    if (det){
        if (cmp((point){x,y},(point){g[rt].x,g[rt].y})) Del(g[rt].l,x,y,det^1);
        else Del(g[rt].r,x,y,det^1);
    }else{
        if (cmp((point){x,y},(point){g[rt].x,g[rt].y})) Del(g[rt].l,x,y,det^1);
        else Del(g[rt].r,x,y,det^1);
    }
    pushup(rt);
}
inline void update(int xmia,int ymia,int xmaa,int ymaa,int W){
    xma=xmaa;yma=ymaa;xmi=xmia;ymi=ymia;Update(1,W);
}
inline void del(int x,int y){
    Del(1,x,y,0);
}
struct Jumper{
    int t,lx,rx,ly,ry;
};
inline Jumper init(int t,int lx,int rx,int ly,int ry){
    return (Jumper){t,lx,rx,ly,ry};
}
vector<Jumper> e[100001];
inline bool cmpid(point a,point b){
    return a.id<b.id;
}
signed main(){
    n=read(),m=read();W=read();H=read();
    for (int i=1;i<=n;i++){
        a[i].x=read(),a[i].y=read();a[i].id=i;
    }
    g[0].mw=g[0].w=make_pair(inf,inf);
    build(root,1,n,0);
    sort(a+1,a+1+n,cmpid);
    for (int i=1;i<=m;i++){
        int p=read(),t=read(),lx=read(),rx=read(),ly=read(),ry=read();
        e[p].push_back(init(t,lx,rx,ly,ry));
    }
    for (int i=1;i<=n;i++){
        P now=g[1].mw;
        dis[now.second]=now.first;
        del(a[now.second].x,a[now.second].y);
        for (int j=0;j<(int)e[now.second].size();j++){
            Jumper v=e[now.second][j];
            update(v.lx,v.ly,v.rx,v.ry,now.first+v.t);
        }
    }
    for (int i=2;i<=n;i++){
        printf("%d\n",dis[i]);
    }
}