P5812 [IOI2019] 天桥题解

chen_03 · 2022-08-31 16:55:37 · 题解

吐槽：我在网上能找到的所有题解，要么对关键性质的阐述过于简洁，让我这个低水平选手看得云里雾里；要么推广关键性质时的说明过少，或是给出了对想出正解毫无帮助的部分分性质，让题解有失严谨性与逻辑性。

题目想让我们找一条最短路径。虽然这张图是平面图，但最短路径不免错综复杂，所以我们先确定基本思路：建图跑 Dijkstra 最短路。

原图的点数可以达到 \mathcal{O}(nm) 级别，直接跑肯定是不行的，我们考虑简化这张图。

我们先考虑一种特殊情况：不存在一座天桥 [l_i,r_i]，满足 l_i<s<r_i 或 l_i<g<r_i（注意全部是严格小于）。也就是说，任意一座天桥的横坐标范围既不 “横跨” 起点（的横坐标），也不 “横跨” 终点（的横坐标）。

在这种情况下，我们有一个关键性质：

性质　存在一条最优路径，满足：若我们自下而上地进入一座天桥，或自上而下地离开一座天桥，那么进入点（或离开点）一定是这座天桥的某个端点。

注 1　“进入” 表示我们之前不在这座天桥上，现在在这座天桥上；“离开” 表示我们之前在这座天桥上，现在不在这座天桥上。不在这座天桥上时，我们可能在某栋建筑上上下移动，也可能在另一座天桥上左右移动。
注 2　“自下而上地进入” 表示我们进入这座天桥之前，我们在某栋建筑上向上移动；“自上而下地离开” 表示我们离开这座天桥之后，我们在某栋建筑上向下移动。
注 3　进入点与离开点都一定在某栋建筑上。

注 4　即使路径与这座天桥只有一个交点（公共点），我们也认为这条路径 “进入” 与 “离开” 了这座天桥各一次。

我们先证明其中一种情况。假设现在有一条最优路径，它自下而上地进入了一座天桥 [l_i,r_i]。天桥 i 满足 s\le l_i（这里是小于等于，也就是天桥 i 位于起点右方），且进入点不是天桥 i 的端点。

有三种情况：进入天桥 i 之后，离开天桥 i 之前，我们

向左移动了一段距离（图 1）；
向右移动了一段距离（图 2）；
没有左右移动（图 3）。

以图 1 的情况为例。如图，S 为起点，AB 为进入天桥 i 前向上移动的那一段，BC 为在天桥 i 上的移动，D 为天桥 i 的右端点。B 不是天桥 i 的端点，C 不一定是天桥 i 的端点。明确 x_S\le x_C，AB>0，BC>0。

若路径 S\rightarrow A 经过了点 C 所在的建筑 X，不妨设 S\rightarrow A 最后一次位于建筑 X 上时在点 E 上，则 E\rightarrow C 的长度严格小于 E\rightarrow A\rightarrow B\rightarrow C 的长度（因为 BC>0），替换一下一定更优。这与 “这条路径是最优路径” 矛盾。

那么 S\rightarrow A 没有经过建筑 X。设 S\rightarrow A 最后一次位于横坐标 x_C 上时在点 F 上，那么 F\rightarrow A 的过程中横坐标始终 \ge x_C。

若 F\rightarrow A 经过了线段 CD，不妨设 F\rightarrow A 最后一次位于线段 CD 上时在点 G 上，由 AB>0 得 G\rightarrow B 的长度严格小于 G\rightarrow A\rightarrow B 的长度，同样推出矛盾。

那么 F\rightarrow A 经过了线段 CD 的延长线。设点 M 为点 D 所在的建筑的底端，由前文可得 F\rightarrow A 经过了线段 DM。

设 F\rightarrow A 最后一次位于线段 DM 上时在点 H 上，那么 H\rightarrow D\rightarrow B 的长度小于等于 H\rightarrow A\rightarrow B 的长度，要么推出矛盾，要么可以把 H\rightarrow A\rightarrow B 调整为 H\rightarrow D\rightarrow B 而总长度不变。

我们发现 D 是天桥 i 的端点。也就是说，我们可以把路径调整为：自下而上地从天桥 i 的端点 D 进入天桥 i。

对于图 2,3 的情况，证明与此类似。图 2 可以调整为从端点 D 进入天桥 i，图 3 可以调整为从端点 D 或端点 E 进入天桥 i。

UPD　这里我想复杂了。考虑天桥与它两端点所在的建筑构成了 “冂” 形，而起点没有被 “冂” 形包住，所以路径必然经过了 “冂” 形，只要讨论路径最后一次位于 “冂” 形上时在三条线段中的哪一条上即可。
两种证法本质相同，但这种显然更简洁。

同理，若天桥 i 满足 r_i\le s（即天桥 i 位于起点左方），也可以类似地调整。对于 “自上而下地离开” 的情况，讨论天桥 i 与终点 g 的位置关系，用对称的方法证明即可。

到这里我们已经证明了，对于一座特定的天桥 i，我们可以把路径调整为（对天桥 i 而言）满足关键性质的状态。考虑对于一条最优路径不断地（每次选择一座天桥）进行这样的调整，若调整能在有限次内结束则性质得证。

由前文的证明可得，一次调整的过程一定形如下图：若对于天桥 i 进行调整，我们只会改变高度不高于天桥 i 的一段路径。所以我们每次选择最高的不合法的天桥调整即可，这样每座天桥最多被调整一次。于是性质得证。

上文中我们讨论的都是 “不存在一座天桥 [l_i,r_i] 满足 l_i<s<r_i 或 l_i<g<r_i” 的情况。对于一般情况，我们尝试进行一些调整，使之符合条件。

若天桥 i 满足 l_i<s<r_i，我们找到与天桥 i 有交的：横坐标最大的满足 X\le s 的建筑 X，和横坐标最小的满足 s\le Y 的建筑 Y。我们把天桥 [l_i,r_i] 拆成三段：[l_i,X]，[Y,r_i]，[X,Y]。前两段都没有 “横跨” 起点 s；对于第三段，可以发现它只与建筑 X,Y 有交，也就是只能通过两个端点进入与离开这座天桥，所以它不可能产生违背关键性质的情况。

对于 l_i<g<r_i 的情况，可以类似地进行拆分。不断地进行这样的拆分即可，天桥的总数仍为 \mathcal{O}(m) 级别。

有了这个关键性质，我们就可以对原图进行简化了。假设我们从天桥 i 出发向下走到天桥 j（没有拐弯，下同），或从天桥 j 出发向上走到天桥 i，不难发现，这一过程中经过的所有位于某座天桥上的点，除天桥 j 上的那个点以外，都一定是某座天桥的端点。因此除起点和终点外，我们只需保留所有天桥的端点，以及每个端点下方第一个位于某座天桥上的点即可。

这样点数和边数都被缩减到了 \mathcal{O}(m) 级别。时间复杂度一个 \log。

如果要问这个关键性质是怎么想到的，按我的理解，大概是对着 s=0，g=n-1 的部分分画画图找找规律，再推广到一般情况吧。

代码写得很丑，仅供参考。

#include <bits/stdc++.h>
#define eb emplace_back
#define ls u<<1
#define rs u<<1|1
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
int n,m,M,S,G,t=1,L,R,x[100005],h[100005],p[100005];
int l[100005],r[100005],y[100005],z[100005];
int ti[400005],a[200015],b[200015],cnt,bg,ed,tot;
vector<pii> vec[100005],e[1200005];
set<int> s;
set<int>::iterator it;
map<int,int> mp[100005];
priority_queue<pli,vector<pli>,greater<pli> > q;
ll dis[1200005];
inline pii calc(int x,pii u,vector<pii> &V){
    it=s.lower_bound(x),R=*it;
    L=*(R^x?--it:it);
    V.eb(pii(u.fi,L)),V.eb(pii(R,u.se));
    u.fi=L,u.se=R;
    return u;
}
void cover(int u,int l,int r,int x,int y,int z){
    if(x<=l && r<=y)return ti[u]=z,void();
    int mid=(l+r)>>1;
    if(x<=mid)cover(ls,l,mid,x,y,z);
    if(y>mid)cover(rs,mid+1,r,x,y,z);
}
int que(int u,int l,int r,int x){
    if(l==r)return ti[u];
    int mid=(l+r)>>1;
    if(x<=mid)return max(ti[u],que(ls,l,mid,x));
    return max(ti[u],que(rs,mid+1,r,x));
}
inline int id(int x,int y){
    if(mp[y].count(x))return mp[y][x];
    return mp[y][x]=++tot;
}
inline void ins(int u,int v,int w){
    e[u].eb(pii(v,w));
    e[v].eb(pii(u,w));
}
inline void work(int k){
    cnt=0;
    for(auto u:vec[k])
        a[++cnt]=u.fi,a[++cnt]=u.se;
    sort(a+1,a+1+cnt);
    cnt=unique(a+1,a+1+cnt)-a-1;
    for(int i=1,u,v;i<=cnt;++i){
        u=id(a[i],k);
        if((v=que(1,1,n,a[i]))==-1)continue;
        ins(u,id(a[i],v),z[k]-z[v]);
    }
    for(auto u:vec[k])
        cover(1,1,n,u.fi,u.se,k);
}
inline void work2(int k){
    cnt=0,t=1;
    for(auto u:mp[k])
        a[++cnt]=u.fi,b[cnt]=u.se;
    sort(vec[k].begin(),vec[k].end());
    for(auto u:vec[k]){
        while(t<=cnt && a[t]<u.fi)++t;
        while(t<cnt && a[t+1]<=u.se)
            ins(b[t],b[t+1],x[a[t+1]]-x[a[t]]),++t;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d%d",x+i,h+i);
        s.insert(i),p[i]=i;
    }
    sort(p+1,p+1+n,[](int X,int Y){
        return h[X]<h[Y];
    });
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",l+i,r+i,y+i);
        ++l[i],++r[i],z[i]=y[i];
    }
    sort(z+1,z+1+m);
    M=unique(z+1,z+1+m)-z-1;
    for(int i=1;i<=m;++i){
        y[i]=lower_bound(z+1,z+1+M,y[i])-z;
        vec[y[i]].eb(l[i],r[i]);
    }
    scanf("%d%d",&S,&G),++S,++G;
    if(S>G)swap(S,G);
    for(int i=1;i<=n*4;++i)ti[i]=-1;
    bg=id(S,0),cover(1,1,n,S,S,0);
    ed=id(G,0),cover(1,1,n,G,G,0);
    for(int k=1;k<=M;++k){
        while(t<=n && h[p[t]]<z[k])s.erase(p[t++]);
        for(int i=0;i<(int)vec[k].size();++i){
            pii u=vec[k][i];
            if(u.fi<S && S<u.se)
                vec[k][i]=calc(S,u,vec[k]);
            else if(u.fi<G && G<u.se)
                vec[k][i]=calc(G,u,vec[k]);
        }
        work(k);
    }
    for(int i=1;i<=M;++i)work2(i);
    for(int i=1;i<=tot;++i)dis[i]=2e18;
    dis[bg]=0,q.push(pli(0,bg));
    while(!q.empty()){
        pli t=q.top();q.pop();
        int u=t.se;
        if(dis[u]<t.fi)continue;
        dis[u]=t.fi;
        for(auto v:e[u]){
            if(dis[v.fi]<=dis[u]+v.se)continue;
            dis[v.fi]=dis[u]+v.se;
            q.push(pli(dis[v.fi],v.fi));
        }
    }
    printf("%lld\n",dis[ed]<1e18?dis[ed]:-1);
    return 0;
}

P5812 [IOI2019] 天桥 题解

P5812 [IOI2019] 天桥题解