\(\def \ra {\rightarrow}\)
解法
1本封鎖されれば，通るべき path が一意に定まる． 相異なる vertices \(a,b \in N\) を固定する．\(a < b\) と仮定してよい． Edge \(e \not\in [a,b)\) を切断したとき，path は \(a \ra a+1 \ra \cdots \ra b\) となり， \(e \in [a,b)\) を切断したとき，path は \(a \ra a-1 \ra \cdots \ra b\) となる．
実装
区間に対する和を保留して，最後にまとめるので，imos 法で解ける．
注意
元のグラフの edge を vertex に， 元のグラフの vertex を 区間の境目と考える．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vll a(m); rep(i,m) { cin >> a[i]; a[i]--; }
vll v(n+1);
// edge in [l,r) を切った場合
auto add = [&](ll l, ll r, ll x) -> void {
if(r < l) swap(l,r);
v[l] += x;
v[r] -= x;
};
rep(i,m-1){
ll s = a[i];
ll t = a[i+1];
if(s > t) swap(s,t);
ll a = t - s;
ll b = n - a;
add(0,s,a); // rem : a
add(s,t,b); // rem : b
add(t,n,a); // rem : a
}
rep(i,n){
v[i+1] += v[i];
}
ll ans = *min_element(v.begin(), v.begin()+n);
cout << ans << endl;
return 0;
}
