1696D. Permutation graph thinking

link
thinking

The question

Give a sequence $a_1,a_2,...,a_n$ by $1～n$ The whole arrangement . $i,j$ There is an undirected edge between if and only if $a_i,a_j$ Exactly $a_i,...,a_j$ The minimum and maximum values of these numbers （ A minimum and a maximum ）. The length of each edge is 1, Ask from $1$ To $n$ What is the shortest distance . $1\le n\le 2.5\times 10^5$.

Ideas

set up $dis(x,y)$ Express $x$ and $y$ The shortest circuit length between .

consider $a_i=n$ The location of , And suppose $i\ne 1,i\ne n$ , obvious , from $1\to n$ , Must go through $i$ spot . In the same way $a_j=1$ The location of , Allied , Must go through $j$ spot , Then there are $$dis(x,y)=dis(1,i)+1+dis(j,n)$$ It's assumed here that $i<j$, If $j>i$ The same goes for . In the middle of the $1$ That is to say $dis(i,j)$, because $a_i,a_j$ Respectively $n$ and $1$, So obviously there are edges that can be reached in one step .

Next, continue the recursive processing $dis(1,i)$ and $dis(j,n)$ . Just find The minimum and maximum values of the interval And continue recursion .

Just preprocess the subscript corresponding to the minimum value of prefix and suffix . Time complexity $O(n)$ .

Code

int n;
int a[maxn], id[maxn];
int l_min[maxn], l_max[maxn];//  front i Minimum number / The subscript of the largest value 
int r_min[maxn], r_max[maxn];//  after n-i Minimum number / The subscript of the largest value 
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;
}