专栏文章

题解：CF1696D Permutation Graph

YYGBC_
CF1696D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9u79u
此快照首次捕获于
2025/12/01 22:55
3 个月前
此快照最后确认于
2025/12/01 22:55
3 个月前
查看原文

Permutation Graph

题意

给出一个 11 到 nn 的排列 [a1,a2,…,an][a_1,a_2,\dots,a_n] 。对于 1≤i<j≤n1\le i < j\le n ，记 mn⁡(i,j)\operatorname{mn}(i,j) 为 min⁡k=ijak\min\limits_{k=i}^j a_k ，记 mx⁡(i,j)\operatorname{mx}(i,j) 为 max⁡k=ijak\max\limits_{k=i}^j a_k 。
有一张 nn 个点的无向图，点的编号为 11 到 nn 。对于每一对整数 1≤i<j≤n1\le i<j\le n ，如果同时满足 mn⁡(i,j)=ai\operatorname{mn}(i,j)=a_i 且 mx⁡(i,j)=aj\operatorname{mx}(i,j)=a_j ，或同时满足 mn⁡(i,j)=aj\operatorname{mn}(i,j)=a_j 和 mx⁡(i,j)=ai\operatorname{mx}(i,j)=a_i ，那么就在 ii 和 jj 之间连一条长度为 11 的边。
询问这张图中从 11 到 nn 的最短路的长度。可以证明 11 和 nn 总是连通，所以最短路总是存在。

分析

推几个性质：
  1. 不可能往回走。 设存在 i≤j≤k≤li\le j\le k\le l，使得 ii 与 jj，jj 与 kk，kk 与 ll 之间存在路径。显然 min⁡(ai,ak)≤aj≤max⁡(ai,ak)\min(a_i,a_k)\le a_j\le\max(a_i,a_k) 并且 min⁡(j,l)≤ak≤max⁡(aj,al)\min(j,l)\le a_k\le\max(a_j,a_l) ，
    这说明 min⁡(ai,aj,ak,al)≤aj,ak≤max⁡(ai,aj,ak,al)\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→k→j→li\rightarrow k\rightarrow j\rightarrow l 的路径都可以简化成 i→li\rightarrow l。
  2. 若数对 l≤rl\le r 能使 aa 的一个连续子序列 al,al+1,...,ara_l,a_{l+1},...,a_r 单调不减或不增，且不可拓展（即 al−1,al+1,...,ara_{l-1},a_{l+1},...,a_r 和 al−1,al+1,…,ar+1a_{l-1},a_{l+1},\dots,a_{r+1} 不满足条件），则下标 i∈[l,r]i\in[l,r] 中只有 l,rl,r 满足条件。 这个也比较显然，因为可以通过直接走最值来简化路径。
  3. 对于刚刚简化得到的折线，尽量向右跳一定最优。 对刚才的折线进行黑白染色，我们发现黑点只能跳到白点，白点只能跳到黑点。假设有白点 ii，黑点 j≤kj\le k，若 ii 能跳到 j,kj,k，显然跳到 kk 最优。因为 jj 在 i,ki,k 之间，跳 kk 不仅距离更远，对后续的贡献肯定更大。

实现

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...