题解：CF1696D Permutation Graph

YGBC_ · 2025-11-12 08:46:15 · 题解

Permutation Graph

题意

给出一个 1 到 n 的排列 [a_1,a_2,\dots,a_n] 。对于 1\le i < j\le n ，记 \operatorname{mn}(i,j) 为 \min\limits_{k=i}^j a_k ，记 \operatorname{mx}(i,j) 为 \max\limits_{k=i}^j a_k 。

有一张 n 个点的无向图，点的编号为 1 到 n 。对于每一对整数 1\le i<j\le n ，如果同时满足 \operatorname{mn}(i,j)=a_i 且 \operatorname{mx}(i,j)=a_j ，或同时满足 \operatorname{mn}(i,j)=a_j 和 \operatorname{mx}(i,j)=a_i ，那么就在 i 和 j 之间连一条长度为 1 的边。

询问这张图中从 1 到 n 的最短路的长度。可以证明 1 和 n 总是连通，所以最短路总是存在。

分析

推几个性质：

不可能往回走。 设存在 i\le j\le k\le l，使得 i 与 j，j 与 k，k 与 l 之间存在路径。显然 \min(a_i,a_k)\le a_j\le\max(a_i,a_k) 并且 \min(j,l)\le a_k\le\max(a_j,a_l) ，

这说明 \min(a_i,a_j,a_k,a_l)\le a_j,a_k\le \max(a_i,a_j,a_k,a_l)。显然形如 i\rightarrow k\rightarrow j\rightarrow l 的路径都可以简化成 i\rightarrow l。
若数对 l\le r 能使 a 的一个连续子序列 a_l,a_{l+1},...,a_r 单调不减或不增，且不可拓展（即 a_{l-1},a_{l+1},...,a_r 和 a_{l-1},a_{l+1},\dots,a_{r+1} 不满足条件），则下标 i\in[l,r] 中只有 l,r 满足条件。这个也比较显然，因为可以通过直接走最值来简化路径。
对于刚刚简化得到的折线，尽量向右跳一定最优。 对刚才的折线进行黑白染色，我们发现黑点只能跳到白点，白点只能跳到黑点。假设有白点 i，黑点 j\le k，若 i 能跳到 j,k，显然跳到 k 最优。因为 j 在 i,k 之间，跳 k 不仅距离更远，对后续的贡献肯定更大。

实现

我们已经证明了尽量向右跳一定最优，那么如何实现？我们预处理出最大（最小）值的 \text{ST} 表，对于每一个下标 i ，只需要找到其右边最小值为 a_i，最大值所在的点，和最大值为 a_i，最小值所在的点，然后取 \text{max} 就可以了，为什么可以这样做呢。首先指定了范围，在范围中最值点之后均不可跳到，所以这样跳最远。取 \text{max} 的原因如性质三。如果不是折线上的点不用考虑，如果是折线上的点，显然取的两点只有一点满足条件。得到每一个点所能跳到的最远点后，直接暴力跳或是动态规划就可以了。

\text{AC Link} ，附代码。

#include<bits/stdc++.h>
using namespace std;

int T;

int N;
int Lg[250005];
int a[250005],b[250005],f[250005];
int stmx[250005][25];
int stmn[250005][25];

void init(){
    for(int i=2;i<=2.5e5;i++)  //预处理出 log x 
        Lg[i]=Lg[i>>1]+1;
}

int find_max(int l,int r){
    int len=Lg[r-l+1];
    return max(stmx[l][len],stmx[r-(1<<len)+1][len]); 
}

int find_min(int l,int r){
    int len=Lg[r-l+1];
    return min(stmn[l][len],stmn[r-(1<<len)+1][len]); 
}

void solve(){
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>a[i];
        stmx[i][0]=stmn[i][0]=a[i];
        b[a[i]]=i;
    }
    for(int j=1;j<=Lg[N];j++)                //预处理ST表 
        for(int i=1;i+(1<<j)-1<=N;i++){
            stmx[i][j]=max(stmx[i][j-1],stmx[i+(1<<j-1)][j-1]);
            stmn[i][j]=min(stmn[i][j-1],stmn[i+(1<<j-1)][j-1]);
        }

    for(int i=1,l,r;i<=N;i++){

        l=i,r=N;
        int pos1=0;
        while(l<=r){         //二分 
            int mid=l+r>>1;
            if(find_min(i,mid)==a[i]) pos1=mid, l=mid+1;
            else r=mid-1;
        }
        int maxn=find_max(i,pos1);
        pos1=b[maxn];       //根据排列的性质，用桶优化 

        l=i,r=N;            //同上 
        int pos2=0;
        while(l<=r){
            int mid=l+r>>1;
            if(find_max(i,mid)==a[i]) pos2=mid, l=mid+1;
            else r=mid-1;
        }
        int minn=find_min(i,pos2);
        pos2=b[minn];

        f[i]=max(pos1,pos2);

    }

    int step=0, nw=1;
    while(nw!=N){
        nw=f[nw];
        step++;
    }
    cout<<step<<'\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
    init(); cin>>T;
    while(T--) solve();
}