問題概要
$0$ から $n - 1$ で番号付けられた $n$ 個の島と $n$ 本の橋があり，$i$ 番の橋は島 $i$ と島 $i + 1 \bmod n$ を双方向に結んでいる．
島 $X_1$ から開始して島 $X_2, X_3, \dots, X_m $ を順に訪れる，「ツアー」というものについて考える（$X$ 上で隣接する $2$ 島を訪れる間に別の島を通ってもよい）．ツアーの「長さ」はツアー中に橋を通る回数である．詳細は原文参照のこと．
ここで，橋を一本落とすことを考える．落とす橋をうまく選んでツアーの長さを最小化したとき，その長さはいくらか？
制約
- $3 \leq n \leq 2 \times 10^5$
- $2 \leq m \leq 2 \times 10^5$
解法
まずは橋を落とす前の状況について考えてみます．ツアーにおいて隣接する $2$ 島 $X_i, X_{ i + 1 }$ 間の移動について考えます．簡単のために $a = \min( X_i, X_{ i + 1 } ), b = \max( X_i, X_{ i + 1 } )$ とすると*1，この $2$ 島間の移動によるツアーの長さへの寄与は，
\begin{align*}
l_1 &= b - a \\
l_2 &= n - l_1
\end{align*}
として $$\min( l_1, l_2 )$$ です．ここで，$l_1 = l_2$ のときは時計回りも反時計回りも*2経由する橋の本数が同じ場合で，どの橋が落ちても迂回ルートも同距離なのでツアーへの寄与は変わりません*3．
では，橋が落ちる場合どうなるでしょうか．時計回り・反時計回りの移動は，片方は橋 $n - 1$ を経由せず，他方は経由します*4．通る橋は，
- 橋 $n - 1$ を通らない移動 : 橋 $a, a + a, \dots, b - 1$ を通る（距離 $l_1$）．
- 橋 $n - 1$ を通る移動 : 橋 $0, 1, a - 1$ 及び橋 $b, b + 1, n - 1$ を通る（距離 $l_2$）．
となります．$l_1 < l_2$ のとき，橋 $a, a + 1, \dots, b - 1$ のいずれかが落ちると，迂回によりツアーの長さが $l_2 - l_1$ 増えます．$l_1 > l_2$ のときは，橋 $0, 1, \dots, a - 1$ 及び橋 $b, b + 1, \dots, n - 1$ が落ちると，迂回によりツアーの長さが $l_1 - l_2$ 増えます．
ツアー上で隣接する全ての $2$ 島について上記値を計算し，全ての橋について損失の和を求めて最小値をとれば，問題の答えが得られます．
複数の橋について損失分を加算する処理は愚直にやると時間がかかり，全体で $O( n m )$ 時間となって（おそらく）*5 TLE しますが，区間への加算だと考えていもす法をすれば，全体で $\Theta( n + m )$ 時間となり間に合います．
コード
int main() { IN( int, N, M ); VI X( M ); cin >> X; transform( ALL( X ), begin( X ), bind( minus< int >(), _1, 1 ) ); VLL used( N + 1 ); LL res = 0; REP( i, M - 1 ) { const int a = min( X[i], X[ i + 1 ] ); const int b = max( X[i], X[ i + 1 ] ); const int l1 = b - a; const int l2 = N - l1; res += min( l1, l2 ); if ( l1 == l2 ) { continue; } if ( l1 < l2 ) { used[a] += l2 - l1; used[b] -= l2 - l1; } else { used[0] += l1 - l2; used[a] -= l1 - l2; used[b] += l1 - l2; used[N] -= l1 - l2; } } partial_sum( ALL( used ), begin( used ) ); cout << res + *min_element( begin( used ), begin( used ) + N ) << endl; return 0; }
