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

LastKismet · 2025-11-10 16:59:51 · 题解

Sol

首先容易想到，每个点与两侧最近的不小于他的点连边，然后跑最短路即可得到答案。考虑最短路径的形式，必然是从等级小的点，走到一个等级最大的点，然后再走向等级更小的点，这样一个峰状。因此我们可以视作是两边同时向峰巅汇集。

考虑分讨三种情况：

• 若最大点在二者中间，那么二者会在各自一侧最少步数走到这一点；
• 若一侧经过了二者中间的最大点，然后二者在另一侧外的更大点汇聚，显然这个更大点应该是这一侧外首个超过中间最大值的点；
• 若二者都先走到了各自一侧外更大点，然后不经过中间最大值直接汇集，那么显然两侧的更大值都应该是最近的超过中间最大值的值。

整合一下，发现每一侧都是要么走到中间最大值，要么走到外向首个超过中间最大值的点。

我们先从左侧点跳尽可能多的步数，使得当前步数左侧点不可能走到右侧点以右，那么现在要么跳到了中间最大值，要么跳到了外向更大值处。

然后从右侧点跳尽可能多的步数，使得当前步数右侧点不可能走到左侧点跳到的位置以左。事实上只需要不可能走到左侧点可能跳到的最右侧位置以左即可，假如左侧点往中间跳显然对，假如往另一侧跳那么右端点不会到中间最大值，右侧点会走到中间最大值处或者外向更大值处。

因此倍增跳就行。显然从区间端点跳不劣于非端点跳转移，因此倍增转移时只用考虑端点即可。

Code

const int N=1e5+5,T=18;

int n,k,q;
int a[N];
int l[N],r[N];
int lt[N][T],rt[N][T];

inline void Main(){
    cin>>n>>k>>q;
    rep(i,1,n)cin>>a[i];
    stack<int> stk;
    rep(i,1,n){
        while(stk.size()&&a[stk.top()]<a[i])stk.pop();
        if(stk.size())l[i]=stk.top();
        else l[i]=1;
        stk.push(i);
    }
    while(stk.size())stk.pop();
    per(i,n,1){
        while(stk.size()&&a[stk.top()]<a[i])stk.pop();
        if(stk.size())r[i]=stk.top();
        else r[i]=n;
        stk.push(i);
    }
    rep(i,1,n)lt[i][0]=l[i],rt[i][0]=r[i];
    repl(t,1,T)rep(i,1,n)lt[i][t]=min(lt[lt[i][t-1]][t-1],lt[rt[i][t-1]][t-1]),rt[i][t]=max(rt[rt[i][t-1]][t-1],rt[lt[i][t-1]][t-1]);
    rep(i,1,q){
        int a,b;cin>>a>>b;
        if(a>b)swap(a,b);
        pii xa={a,a},xb={b,b};
        int res=0;
        per(t,T-1,0){
            int l=min(lt[xa.fir][t],lt[xa.sec][t]);
            int r=max(rt[xa.fir][t],rt[xa.sec][t]);
            if(r<b)res+=1<<t,xa={l,r};
        }
        per(t,T-1,0){
            int l=min(lt[xb.fir][t],lt[xb.sec][t]);
            int r=max(rt[xb.fir][t],rt[xb.sec][t]);
            if(l>xa.sec)res+=1<<t,xb={l,r};
        }
        put(res);
    }
}