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

qcf2010 · 2026-10-22 16:50:04 · 题解

思路

问题需要我们最小化停靠站数量，那我们可以思考：对于每一个站点，在一个站点都不停靠的情况下，往左走最远可以走到哪个站点，往右走最远可以走到哪个站点。

设上面两个要求的量为 p_i 和 q_i，因为要保证路途中不停靠任何站点，因此路途中的任何站点的等级都不能比出发站点的等级高，于是我们可以使用单调栈求出。

所以对于任意两个站点间的来往，一次停靠即可视作在 p 和 q 上“跳跃“一次，因此我们可以使用倍增提升效率。设 l_{i,j} 表示从站点 i 停靠 2^j 次最左可以到达哪个站点，r_{i,j} 表示从站点 i 停靠 2^j 次最右可以到达哪个站点，那么显然，l_{i,0}=p_i,r_{i,0}=q_i，并有：

为什么要取最大和最小呢？因为一直往一个方向走不一定就是最优的（如样例 1 第二个询问的最优解）。还可以这样理解：区间 [l_{i,j},r_{i,j}] 表示的是从站点 i 出发“跳跃” 2^j 次能够到达的站点范围，现在要向外扩展，必然是取这个区间的全局最优。

预处理出 l 和 r 后，对于每组询问，我们可以这样处理：设起点和终点分别为 s 和 e（s\le e），从 s 开始，利用 l 和 r 扩展能到达的区间 [x,y]，并保证 y<e；再从 e 开始扩展区间 [u,v]，保证 y<u。此时 y 和 u 之间虽可能不相邻，但保证了从 y 到 u 不需要停靠任何站点，因此最终的答案便是两次扩展次数之和。

代码

::::success[AC]

#include<bits/extc++.h>
using namespace std;
const int N=1e5+10,L=20;

int n,k,q;
int a[N];

int lim;
int l[N][L],r[N][L];

void Init(){
    stack<int> stk;
    for(int i=1;i<=n;++i){
        while(stk.size()&&a[stk.top()]<a[i]) stk.pop();
        l[i][0]=stk.size()?stk.top():i;
        stk.push(i);
    }
    while(stk.size()) stk.pop();
    for(int i=n;i>=1;--i){
        while(stk.size()&&a[i]>a[stk.top()]) stk.pop();
        r[i][0]=stk.size()?stk.top():i;
        stk.push(i);
    }
    lim=log2(n)+1;
    for(int j=1;j<=lim;++j){
        for(int i=1;i<=n;++i){
            l[i][j]=min(l[l[i][j-1]][j-1],l[r[i][j-1]][j-1]);
            r[i][j]=max(r[l[i][j-1]][j-1],r[r[i][j-1]][j-1]);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k>>q;
    for(int i=1;i<=n;++i) cin>>a[i];
    Init();
    while(q--){
        int res=0,st,ed; cin>>st>>ed;
        if(st>ed) swap(st,ed);
        int x=st,y=st;
        for(int i=lim;i>=0;--i){
            int nx=min(l[x][i],l[y][i]),ny=max(r[x][i],r[y][i]);
            if(ny<ed){
                x=nx; y=ny;
                res+=(1<<i);
            }
        }
        int u=ed,v=ed;
        for(int i=lim;i>=0;--i){
            int nu=min(l[u][i],l[v][i]),nv=max(r[u][i],r[v][i]);
            if(y<nu){
                u=nu; v=nv;
                res+=(1<<i);
            }
        }
        cout<<res<<"\n";
    }

    return 0;
}

::::