题解：P14387 [JOISC 2017] 火车旅行 / Railway Trip

· · 题解

P14387 [JOISC 2017] 火车旅行 / Railway Trip 题解

题意简述

有 n 个车站，第 i 个车站的等级为 l_i \in [1,k]。共有 k 种火车，第 i 种火车会在所有等级不低于 i 的车站停靠，不在其他车站停靠。

列车双向运行。乘客可以在停靠站换乘任意种类的列车，也可以乘坐与目的地方向相反的列车，或经过目的地。要求从车站 x 到车站 y 的路线中，中间停靠站数量最少。

起点站的首次停靠和终点站的最后一次停靠不计入中间停靠站；若乘客在中间站下车换乘，则计一次停靠。

思路分析

先考虑最优解的形状。一定存在一种最优解，使得途经车站的等级序列是单峰的（非严格），这一点比较直观：假设在最后一段下降前，存在一段先下降后上升的部分，那么将这段的左右端点直接连接一定不劣。因此，最优解的形状一定可以先上升再下降。赛时思路止步于此。

这样，问题可以转化为：两条路径分别在某个顶峰处汇聚。对称地，从 x 和 y 出发所经过的路径都可以看作单调不降的。因此，可以让每个点向它左右两侧第一个等级不小于它的点连边，跑全源最短路，时间复杂度为 O(n(n+q))。

接下来考虑如何优化。经过观察可以发现：随着步数增加，从某个点出发能够到达的最左点编号单调不增，最右点编号单调不减。

取 x 向外走 a 次，y 向外走 b 次。我们维护能够到达的最左、最右端点所包含的区间。如果这两个区间不交，则说明此时一定还不能交汇。

于是可以用倍增处理：预处理一个车站走 2^i 步能够到达的包含区间。查询时，倍增地取使得 x 和 y 到达区间保持不交的最大步数，再加 1，就是经过的边数；再减去 1，得到答案，即使得 x 和 y 到达区间最大不交的步数。

这里可能会对正确性产生疑问：实际到达的点可能是离散的，会不会出现区间恰好相交之后却仍然无法交汇的情况？

实际上不会。证明如下：不妨设 x<y，假设 x 可以到达 [l_1,r_1]，y 可以到达 [l_2,r_2]，且 l_2 \le r_1。直观上，l_2 和 r_1 本质上分别是一条递增链的链顶。若区间相交之后两条链仍无法接上，也就是两条链发生交叉。不妨设 l_2 后面接上的链顶为 t_1，r_1 接上的链顶为 t_2。由于我们保证了初始两个区间不交，那么加入的这两个链顶一定在加入前这两个区间之间的空缺中，否则会违反链上单调增的性质，即链顶的等级在路径中最大。因此，t_1 和 t_2 中的较大值一定可以接上两条链。这样便证明了可达区间相交等价于路径可以交汇。

最优性方面，查询中维护的是可达范围的最左、最右端点；若少走步数，可达范围只会缩小，不可能更早接上。因此，贪心取最大不交步数不会漏解。

至此，算法分析完成。时间复杂度为 O((n+q)\log n)。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,LG=22;
#define pii pair<int,int>
#define fi first
#define se second
int n,q,k,a[N];
pii t[N][LG];
void init()
{
    stack<int> s;
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&a[i]>a[s.top()]) s.pop();
        if(s.empty()) t[i][0].fi=1;
        else t[i][0].fi=s.top();
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n;i>=1;i--)
    {
        while(!s.empty()&&a[i]>a[s.top()]) s.pop();
        if(s.empty()) t[i][0].se=n;
        else t[i][0].se=s.top();
        s.push(i);
    }
    for(int j=1;j<LG;j++)
    {
        for(int i=1;i<=n;i++)
        {
            int l=t[i][j-1].fi,r=t[i][j-1].se;
            t[i][j].fi=min(t[l][j-1].fi,t[r][j-1].fi);
            t[i][j].se=max(t[l][j-1].se,t[r][j-1].se);
        }
    }
}
int query(int x,int y)
{
    int res=0;
    pii X={x,x},Y={y,y};
    for(int i=LG-1;i>=0;i--)
    {
        int l=min(t[X.fi][i].fi,t[X.se][i].fi),r=max(t[X.fi][i].se,t[X.se][i].se);
        if(r<Y.fi)
        {
            res+=(1<<i);
            X={l,r};
        }
    }
    for(int i=LG-1;i>=0;i--)
    {
        int l=min(t[Y.fi][i].fi,t[Y.se][i].fi),r=max(t[Y.fi][i].se,t[Y.se][i].se);
        if(l>X.se)
        {
            res+=(1<<i);
            Y={l,r};
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    init();
    for(int i=1;i<=q;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        cout<<query(x,y)<<'\n';
    }
    return 0;
}