题解：AT_joisc2017_f 鉄道旅行 (Railway Trip)

· · 题解

AT_joisc2017_f 鉄道旅行 (Railway Trip) 题解

题目大意

给 1 - k 辆列车编号，它们在含有 n 个站点的轨道上运行，第 j 辆列车只在乘客流量 L _ {i} \ge j 时停车。车可以向前向后走，每次给一个起点站和终点站，问最小停车次数。

寻找思路

先看数据范围 n \le 10 ^ {5}，q \le 10 ^ {5}，由此大概推算出我们的时间复杂度为 O(q \log n)。

当然说不定有什么 O(q\sqrt{n}) 的神奇做法，我想不到而已 qwq。

根据题面和猜测的时间复杂度开始想思路，首先我们发现这个停站特别有意思。比如如果从 1 开始出发，中间 2,3,4 站跳过，直接到站 5。从 1 直接跳到了 5，我们发现它的操作特别像倍增那样，跳来跳去，而且刚好倍增一次的时间就是 O(\log n) 的。

那么我们能否定义一个数组 st[i][j] 表示从第 i 站往后停 2 ^ {j} 次方次所能到达的最远点去做呢？

这显然是不行的，因为车是能够往回走的。

那这时也有一个很显然的做法，就是弄出两个倍增数组。一个记录停 2 ^ {j} 次方次到达的最左边的地方，右边同理。

推公式的时候要注意，因为乘客流量不是单调的，所以能够到达最左的点可能会从右边转移，右边同理。其它的就和正常倍增预处理一样了。

那既然数组都出来了，做法也很明显了。起始点和终点同时往左右两边跳，形成一个区间，表示它停有限次能到达的范围。

如果两个区间有重叠部分，那么结束并输出答案。

注意：我们是边跳边统计答案，而且我们在模拟时是不需要将区间相交的。如果我们相交区间，就需要在 2 ^ {i} 与 2 ^ {i+1} 之间枚举验证答案，与我们预想的时间复杂度不符。所以我们只需要刚好让两个区间不相交，最后它们跳一步就可以相交。而且我们不需要加 1 因为停站不含该旅客的起终点站(由题)。

代码

独特的无意义离线写法

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,k,q;
int l[N],a[N],b[N];
int lft[N][35],rig[N][35];
stack<int>st,st2;
signed main(){
    cin>>n>>k>>q;
    for(int i=1;i<=n;i++) cin>>l[i];
    for(int i=1;i<=q;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++){
        while(st.size()&&l[st.top()]<l[i]) st.pop();
        if(st.size()) lft[i][0]=st.top();
        else lft[i][0]=i;
        st.push(i);
    }
    for(int i=n;i>=1;i--){
        while(st2.size()&&l[st2.top()]<l[i]) st2.pop();
        if(st2.size()) rig[i][0]=st2.top();
        else rig[i][0]=i;
        st2.push(i);
    }
    for(int j=1;j<=30;j++){
        for(int i=1;i<=n;i++){
            lft[i][j]=min(lft[lft[i][j-1]][j-1],lft[rig[i][j-1]][j-1]);
            rig[i][j]=max(rig[lft[i][j-1]][j-1],rig[rig[i][j-1]][j-1]);
        }
    }
    //int ans=0;
    for(int i=1;i<=q;i++){
        if(a[i]>b[i]) swap(a[i],b[i]);
        int ans=0;
        int p1,p2=p1=a[i];
        for(int j=30;j>=0;j--){
            int u=min(lft[p1][j],lft[p2][j]),v=max(rig[p1][j],rig[p2][j]);
            if(v<b[i]) p1=u,p2=v,ans+=pow(2,j);
        }
        a[i]=p2,p1=p2=b[i];
        for(int j=30;j>=0;j--){
            int u=min(lft[p1][j],lft[p2][j]),v=max(rig[p1][j],rig[p2][j]);
            if(u>a[i]) p1=u,p2=v,ans+=pow(2,j);
        }
        cout<<ans<<endl;
    }
    return 0;
}