1696D. Permutation Graph 思维

link
思维

题意

给出一个序列 $a_1,a_2,...,a_n$ 为 $1～n$ 的全排列。 $i,j$ 之间存在一条无向边当且仅当 $a_i,a_j$ 恰好是 $a_i,...,a_j$ 这些数的最小值和最大值（一个最小一个最大）。每条边的长度均为1，问从 $1$ 到 $n$ 最短距离是多少。 $1\le n\le 2.5\times 10^5$。

思路

设 $dis(x,y)$ 表示 $x$ 和 $y$ 之间的最短路长度。

考虑 $a_i=n$ 的位置，并假设 $i\ne 1,i\ne n$ ，显而易见的，从 $1\to n$ ,必须要经过 $i$ 点。同理考虑 $a_j=1$ 的位置，类似的，必须经过 $j$ 点，则有 $$dis(x,y)=dis(1,i)+1+dis(j,n)$$这里假设了 $i<j$，如果 $j>i$ 的话也一样。中间的 $1$ 即为 $dis(i,j)$，因为 $a_i,a_j$ 分别为 $n$ 和 $1$，所以显然有边可以一步到达。

接下来继续递归处理 $dis(1,i)$ 和 $dis(j,n)$ 。只要找到区间的最小值和最大值并继续递归就可以了。

只需要预处理前缀和后缀的最小值对应的下标就可以了。 时间复杂度 $O(n)$ 。

代码

int n;
int a[maxn], id[maxn];
int l_min[maxn], l_max[maxn];//	前i个数最小/最大的值的下标
int r_min[maxn], r_max[maxn];// 后n-i个数最小/最大的值的下标
int dfs(int l, int r) {
	if(l == r) return 0;
	if(l != 1 && r != n) return 1;
	int L, R;
	if(l == 1) {
		L = min(l_min[r], l_max[r]);
		R = max(l_min[r], l_max[r]);
	}
	else {
		L = min(r_min[l], r_max[l]);
		R = max(r_min[l], r_max[l]);
	}
	if(l == L && r == R) return 1;
	return dfs(l, L) + dfs(L, R) + dfs(R, r);
}
void solve() {
    cin >> n;
    l_min[0] = r_min[n+1] = INF;
    l_max[0] = r_max[n+1] = 0;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    	l_min[i] = min(l_min[i-1], a[i]);
    	l_max[i] = max(l_max[i-1], a[i]);
    	id[a[i]] = i;
    }
    for(int i = n; i; i--) {
    	r_max[i] = max(r_max[i+1], a[i]);
    	r_min[i] = min(r_min[i+1], a[i]);
    	// cout << l_max[i] << endl;
    }
    for(int i = 1; i <= n; i++) {
    	l_min[i] = id[l_min[i]];
    	r_min[i] = id[r_min[i]];
    	l_max[i] = id[l_max[i]];
    	r_max[i] = id[r_max[i]];
    	// cout << l_min[i]<<endl;
    }
	cout << dfs(1, n) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43