题解

当 $s=0$ 时，只需考虑每个空隙的贡献就能得到一个可以 $O(n)$ 计算的式子：对于空隙 $(i,i+1)$，它的贡献就是 $2\left(\sum_{j=0}^i [p_j>i]\right)$。此外，如果刚才那个式子为 $0$ 但 $p_{(i+1)\dots n}$ 中有某个位置 $j$ 满足 $p_j\neq j$，那么答案还需额外加上 $2$。

当 $s\neq 0$ 时，上面所说的式子在某些情况下是不对的，因为可能需要一些额外的步骤来空着手移动（例如 $n=4,s=2$ 且 $p=[3,2,1,0]$）。

我们考虑排列中所有的环。对于一个环 $C$，设 $l_C,r_C$ 分别表示 $C$ 中下标的最小、最大值。我们称环 $C_1$ 包含 $C_2$，当且仅当 $\exists x\in C_2,l_{C_1}<x<r_{C_1}$。

有如下性质：

• 对于两个互相包含的环 $C_1,C_2$，从任意在 $C_1,C_2$ 中的位置开始，将 $C_1,C_2$ 中的元素都放到正确的位置，都不需要额外的移动。这是因为如果我们从 $C_1$ 上的某个位置开始，当我们在排序 $C_1$ 的过程中碰到了任意一个 $C_2$ 中的位置，我们就直接将手中的书放到这个位置并开始排序 $C_2$。当 $C_2$ 排序完毕时，我们也回到了这个位置，可以继续排序 $C_1$。这个过程中没有额外移动。
• 可以花费两次额外的移动，来从序列中的某个位置移动到相邻的位置。

根据第一条性质，我们将所有互相包含的环缩成一个，剩下的环要不然包含要不然不交，形成了一棵树。

所以我们从 $[s,s]$ 这个区间开始扩展。每次暴力向左、右分别扩展，并记录代价，直到跳到父亲节点，或者跳到覆盖了整个排列。若跳到了父亲节点，则将答案加上向左、右扩展的代价的较小值；若跳到覆盖整个排列，则需要将答案加上左右扩展的代价之和。

总的时间复杂度是 $O(n)$。

代码

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
using ll = long long;
const int N = 1e6 + 5;
int n, p[N], bel[N], lp[N], rp[N], vis[N];
void Extend(int& l, int& r) {
	int lpos = min(lp[bel[l]], lp[bel[r]]), rpos = max(rp[bel[l]], rp[bel[r]]);
	while (l > lpos || r < rpos) {
		if (l > lpos) {
			lpos = min(lp[bel[--l]], lpos);
			rpos = max(rp[bel[l]], rpos);
		} else {
			lpos = min(lp[bel[++r]], lpos);
			rpos = max(rp[bel[r]], rpos);
		}
	}
}
ll minimum_walk(vector<int> _p, int s) {
	n = _p.size(); ll ans = 0, tot = 0;
	For(i, 0, n - 1) p[i] = _p[i];
	int lmost = s, rmost = s, l = s, r = s;
	For(i, 0, n - 1) ans += abs(p[i] - i);
	For(i, 0, n - 1) if (!vis[i]) {
		lp[++tot] = i;
		for (int u = i; !vis[u]; u = p[u]) {
			vis[u] = 1, bel[u] = tot;
			rp[tot] = max(rp[tot], u);
		}
		if (p[i] != i) lmost = min(lmost, lp[tot]), rmost = max(rmost, rp[tot]);
	}
	while (true) {
		Extend(l, r);
		int lp = l, rp = r, lq = l, rq = r, lcost = 0, rcost = 0;
		while (lp > lmost && rp == r) Extend(--lp, rp), lcost += 2;
		while (rq < rmost && lq == l) Extend(lq, ++rq), rcost += 2;
		if (rp == r) { ans += lcost + rcost; break; }
		ans += min(lcost, rcost), l = lp, r = rp;
	}
	return ans;
}