题解 P5471 【[NOI2019]弹跳】

· · 题解

卡空间还行。

那我把自己的思路讲讲吧。

算法 1：暴力

直接暴力，时间 O(nm)，期望得分 32pts

算法 2：线段树优化建图

不难发现这是一个二维的线段树优化建图。

我比较垃圾，不会线段树套 Treap，我讲一个动态开点线段树的做法。

先对于每个 x 坐标相同的数建一棵线段树，然后像普通线段树 id_{lson}=id_{x}\times 2,id_{rson}=id_{x}\times 2+1 的方式把这些点找出来，对于这些点再建一棵线段树，询问时左右端点要在 vector 上二分一下。（可能比较抽象，最好自己画图理解一下）

不难发现这样时间 O(n\log^2 n)，空间 O(n\log^2 n)，完美被卡，期望得分 88pts

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
const int maxn=70000+10;
const int inf=0x3f3f3f3f;
int n,m,w,h,x[maxn],y[maxn],rt[maxn],ls[maxn*20],rs[maxn*20],sz,cnt;
int dis[maxn*40];bool vis[maxn*40];vector<pii> G[maxn*40];
vector<pii> P[maxn],p[maxn<<2];

inline int read()
{
    register int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return (f==1)?x:-x;
}

inline void addedge(int x,int y,int w)
{
   G[x].pb(mp(y,w));
}

void update(int &x,int l,int r,int pos,int city)
{
    if(!x) x=++sz;
    if(l == r) {addedge(x,city,0);return;}
    int mid=(l+r)>>1;
    if(pos <= mid) update(ls[x],l,mid,pos,city);
    else update(rs[x],mid+1,r,pos,city);
}
void dfs(int x,int rt,int line)
{
    p[rt].pb(mp(line,x));
    if(ls[x]) addedge(x,ls[x],0),dfs(ls[x],rt<<1,line);
    if(rs[x]) addedge(x,rs[x],0),dfs(rs[x],rt<<1|1,line);
}
int T[maxn<<2],lc[maxn*60],rc[maxn*60],L,R,D,U,Pos,Time;
void buildtree(int x,int rt,int l,int r)
{
    if(l == r) {addedge(x,p[rt][l].second,0);return;}
    lc[x-cnt]=++sz,rc[x-cnt]=++sz;
    addedge(x,lc[x-cnt],0),addedge(x,rc[x-cnt],0);
    int mid=(l+r)>>1;
    buildtree(lc[x-cnt],rt,l,mid);
    buildtree(rc[x-cnt],rt,mid+1,r);
}
void build(int l,int r,int rt)
{
    if(!p[rt].empty())
    {
        T[rt]=++sz;
        buildtree(T[rt],rt,0,(int)p[rt].size()-1);
    }
    if(l == r) return ;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void getrow(int x,int L,int R,int l,int r)
{
    if(L <= l && r <= R) {addedge(Pos,x,Time);return;}
    int mid=(l+r)>>1;
    if(L <= mid) getrow(lc[x-cnt],L,R,l,mid);
    if(R > mid) getrow(rc[x-cnt],L,R,mid+1,r);
}
void getline(int l,int r,int rt)
{
    if(D <= l && r <= U)
    {
        if(!p[rt].empty())
        {
            int left=lower_bound(p[rt].begin(),p[rt].end(),mp(L,0))-p[rt].begin();
            int right=lower_bound(p[rt].begin(),p[rt].end(),mp(R+1,0))-p[rt].begin()-1;
            if(left<=right) getrow(T[rt],left,right,0,(int)p[rt].size()-1);
        }
        return ;
    }
    int mid=(l+r)>>1;
    if(D <= mid) getline(l,mid,rt<<1);
    if(U > mid) getline(mid+1,r,rt<<1|1);
}
inline void spfa()
{
    memset(dis,inf,sizeof(dis));
    queue<int> q;
    dis[1]=0;vis[1]=1;q.push(1);
    int u,v;
    vector<pii>::iterator it;
    while(!q.empty())
    {
        u=q.front(),q.pop();vis[u]=0;
        for(it=G[u].begin();it!=G[u].end();it++)
        {
            v=it->first;
            if(dis[v]>dis[u]+it->second)
            {
                dis[v]=dis[u]+it->second;
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
}

int main()
{
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    n=read(),m=read(),w=read(),h=read();
    for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),P[x[i]].pb(mp(y[i],i));
    sz=n;
    vector<pii>::iterator it;
    for(int i=1;i<=w;i++)
    {
        for(it=P[i].begin();it!=P[i].end();it++)
            update(rt[i],1,h,it->first,it->second);
        if(rt[i]) dfs(rt[i],1,i);
    }
    cnt=sz;
    build(1,h,1);
    for(int i=1;i<=m;i++)
    {
        Pos=read(),Time=read(),L=read(),R=read(),D=read(),U=read();
        getline(1,h,1);
    }
    spfa();
    for(int i=2;i<=n;i++) printf("%d\n",dis[i]);
    return 0;
}

至于为什么我写了 spfa。。。主要是图是你自己建的，不是出题人给的，一般不会卡，直接头铁准没错。

算法 3：KD 树优化建图

如果用 KD 树优化建图，点数 O(n) ，边数 O(m\sqrt n)，直接爆炸，期望得分 88pts

虽然我不知道为什么我直接暴力 KD 树 WA 了 3 个点

算法 4：优化算法 3

其实就是把空间降下来。

我们考虑用 dijkstra。一个点只会被更新一次，这样的话就好做了。

我们在 KD 树上维护两个标记 tag,val，分别表示全局更新的最小值和当前点的最小值，两个标记取个 min 就是当前点的答案。

然后我们在每个点再维护一个 mn,id，表示子树内的最小答案和最小答案所在的编号。

难道我们用 KD 树打一下标记就做完了？

那还是有一些细节/剪枝的。

时间 O(m\sqrt n)，空间 O(n)，期望得分 100pts

Code\ Below: 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int maxn=70000+10;
const int inf=0x3f3f3f3f;
int n,m,w,h,rt,D,L,R,X,Y,Pos,Time,ans[maxn],sta[maxn],top;

struct Edge
{
    int t,l,r,x,y;
};
vector<Edge> G[maxn];

inline int read()
{
    register int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return (f==1)?x:-x;
}

struct node
{
    int d[2],id;
}a[maxn];
inline bool operator < (const node &a,const node &b) {return a.d[D]<b.d[D];}

struct KD_Tree
{
    int Max[2],Min[2],d[2],ch[2],fa,id,w,tag,val;pii mn;
    inline void get(const node &a)
    {
        Max[0]=Min[0]=d[0]=a.d[0];
        Max[1]=Min[1]=d[1]=a.d[1];
        fa=0;id=a.id;w=1;tag=val=inf;mn=mp(inf,inf);
    }
}t[maxn];

template <class T> inline void chkmax(T &x,T y) {x=(x>y)?x:y;}
template <class T> inline void chkmin(T &x,T y) {x=(x<y)?x:y;}
inline void update(int x,int y)
{
    chkmax(t[x].Max[0],t[y].Max[0]);
    chkmax(t[x].Max[1],t[y].Max[1]);
    chkmin(t[x].Min[0],t[y].Min[0]);
    chkmin(t[x].Min[1],t[y].Min[1]);
}
inline void pushup(int x)
{
    t[x].mn=mp(t[x].w?min(t[x].tag,t[x].val):inf,t[x].w?x:inf);
    if(t[x].ch[0]) chkmin(t[x].mn,t[t[x].ch[0]].mn);
    if(t[x].ch[1]) chkmin(t[x].mn,t[t[x].ch[1]].mn);
    if(t[x].mn.second!=inf) chkmin(t[x].mn.first,t[x].tag);
}
inline void pushdown(int x)
{
    if(t[x].ch[0]) chkmin(t[t[x].ch[0]].tag,t[x].tag);
    if(t[x].ch[1]) chkmin(t[t[x].ch[1]].tag,t[x].tag);
}
int build(int l,int r,int now)
{
    int mid=(l+r)>>1,x=mid;D=now;
    nth_element(a+l,a+mid,a+r+1);t[x].get(a[mid]);
    if(l<mid) t[x].ch[0]=build(l,mid-1,now^1),t[t[x].ch[0]].fa=x;
    if(mid<r) t[x].ch[1]=build(mid+1,r,now^1),t[t[x].ch[1]].fa=x;
    if(t[x].ch[0]) update(x,t[x].ch[0]);
    if(t[x].ch[1]) update(x,t[x].ch[1]);
    pushup(x);return x;
}
void query(int x)
{
    if(!x || t[x].tag < Time) return ;
    if(t[x].Max[0] < L || t[x].Min[0] > R
    || t[x].Max[1] < X || t[x].Min[1] > Y) return ;
    if(L <= t[x].Min[0] && t[x].Max[0] <= R
    && X <= t[x].Min[1] && t[x].Max[1] <= Y)
    {
        chkmin(t[x].tag,Time);
        pushup(x);
        return ;
    }
    pushdown(x);
    if(L <= t[x].d[0] && t[x].d[0] <= R
    && X <= t[x].d[1] && t[x].d[1] <= Y) chkmin(t[x].val,Time);
    query(t[x].ch[0]);query(t[x].ch[1]);pushup(x);
}

int main()
{
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    n=read(),m=read(),w=read(),h=read();
    for(int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read(),a[i].id=i;
    rt=build(2,n,0);
    for(int i=1;i<=m;i++)
    {
        Pos=read(),Time=read(),L=read(),R=read(),X=read(),Y=read();
        G[Pos].push_back((Edge){Time,L,R,X,Y});
    }
    int x,y;
    vector<Edge>::iterator it;
    for(int i=1;i<=n;i++)
    {
        if(i==1) x=1,y=0;
        else
        {
            y=t[rt].mn.second;t[y].w=0;
            x=t[y].id;ans[x]=t[rt].mn.first;top=0;
            for(;y;y=t[y].fa) sta[++top]=y;
            for(int j=top;j;j--) pushdown(sta[j]);
            for(int j=1;j<=top;j++) pushup(sta[j]);
        }
        for(it=G[x].begin();it!=G[x].end();it++)
        {
            Time=ans[x]+it->t,L=it->l,R=it->r,X=it->x,Y=it->y;
            query(rt);
        }
    }
    for(int i=2;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

总结：如果空间比较松的话，这题算是一道裸题。不过这题线性空间的做法还是值得思考的。