题解：P13524 [KOI 2025 #2] 跳跃

· · 题解

首先，相邻两个数之差一定在集合 \{-2,0,2\} 中。

因为折返的地点不能重复，一次折返有可能使相邻两个数之差增加 2 或者减少 2。

然后考虑一些简单情况。假设输入为 1 3 5 7 9 7 5 3 1，那么我们一定是会的，只需要从第一个点开始跳到后面，然后反复横跳就行。具体来讲，输出为 1 9 2 8 3 7 4 6 5 10。

那么把两个上述的结构拼起来是不是也可以做？输入为 1 3 5 3 1 3 5 3 1，实际上也只是把两段的答案拼起来就行。输出为 1 5 2 4 3 9 6 8 7 10。

以上的结构是否可以嵌套？比如输入为 1 3 5 7 5 3 5 7 5 3 1，实际上就是把 1 3 5 3 1 3 5 3 1 嵌套进了 1 3 3 1 里。可以考虑先处理最前面的 1 3 以及最后的 3 1，就是从刚开始跳到最后，然后再跳回来。然后发现剩下的数 5 7 5 3 5 7 5 就是“把两个上述的结构拼起来”的结构了。这种情况输出 1 11 2 6 3 5 4 10 7 9 8 12。

那么算法就明朗起来了：如果可以找到所谓的“嵌套”，我们有一种比较好的算法（就是跳过去再跳回来）去剥离掉这个“嵌套”，这个时候我们面对的实际上就是一个更小规模的相同的问题，所以可以通过递归的方式大事化小，小事化了。

定义函数 solve(l,r) 表示我们需要计算 [l,r] 这个区间的答案。

考虑两个相邻的数 c_x 和 c_{x+1}，如果 c_{x+1}=c_x+2，可以找到一个位置 y，使得 c_{x+1},c_{x+2},\cdots,c_y 都大于 c_x，且 c_{y+1}=c_x。这个时候我们相当于找到了一个“嵌套”，只需要先跳到 y+1，再跳回 x+1，剥离嵌套后往下调用就行。

那么对于一段 [l,r]，一定可以拆成若干个满足条件的可以向下递归的嵌套。

这样，我们只需要算出对于一个数 x，往后第一个等于 x 的下标 to_x，这样就可以快速找到满足以上要求的下标了。

实现是非常简单的。注意到每个 (i,to_i) 对只会最多考虑 1 次，所以时间复杂度 O(N)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
constexpr ll maxn=2e5+5;
ll n,arr[maxn],to[maxn];
vector<ll> buc[maxn];
void solve(ll l,ll r){
    if(r<l)return;
    for(int i=to[l],pre=l;i && i<=r;pre=i,i=to[i]){
        if(i!=pre+1)cout<<i<<" "<<pre+1<<" ";
        else cout<<i<<" ";
        solve(pre+1,i);
    }
}
int main(){
    //freopen("paper.in","r",stdin);
    //freopen("paper.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        buc[arr[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<buc[i].size();j++){
            to[buc[i][j-1]]=buc[i][j];
        }
    }
    cout<<1<<" ";
    solve(1,n-1);
    cout<<n<<" ";
    return 0;
}