公開日 :
更新日 :

i 番目だけ変えたらどうなるか（前後から累積）

「列のうち i 番目だけ変えたとき全体でどうなるか？ 全ての i で答えよ」系の問題は、前後から累積和を取るとうまくいくことがある。

「i 番目より前」と「i 番目より後ろ」の結果を表にしておき、i ごとに 2 つをつなげる。
i ごとに全体を計算し直すと O(N²) だが、表があれば 1 つの i が O(1) になり、全体で O(N)。

問題文が次の形なら、この方法を疑う。

  • 「どれか 1 つを除く／書き換える／反転する」とき、答えを最大（最小）にせよ
  • 「各 i について、A_i を除いたときの〇〇を答えよ」

使える条件

前半の結果と後半の結果から、全体の結果が O(1) で作れるとき使える。

まとめる操作全体 =問題例
最大・最小max(前, 後ろ) / min(前, 後ろ)ABC483 D
和・個数前 + 後ろABC098 C、 ABC334 C
GCDgcd（前、後ろ)ABC125 C

最大・最小・GCD は「1 個足す」はできるが「1 個抜く」はできない。
だから「全体から A_i を抜く」ではなく、前と後ろを別々に作ってつなげる。
（和だけは引き算で抜けるので、全体 − A_i でも済むことがある）

3 つの形

形i ごとの答え例
i を取り除く前[i -1]と後ろ[i+1]をつなげるABC125 C（1つを好きな数に変える = 実質取り除く）
i を境目に左右で別の数え方をする前[i – 1]と後ろ[i+1]を足すABC098 C（左は W を数え、右は E を数える）
i を変えると後ろ全体がずれる前[i – 1] と（後ろ[i]をずらしたもの）をつなげるABC483 D（後ろの位置がすべて -2A_i ずれる）

なぜ後ろから作るのか

端が固定されている側から作り始めると、範囲が 1 個ずつ増えるだけになる。

表範囲固定されている端作る向き
前[i]先頭 〜 i先頭前から（i を増やす）
後ろ[i]i 〜 最後最後後ろから（i を減らす）
後ろ[i] = op(後ろ[i+1], A[i]);   // すでにある後ろ[i+1] に A[i] を 1 個足すだけ

前から後ろ[i] を作ろうとすると、範囲が左から 1 個ずつ減っていく。
最大などは「抜く」ができないので、毎回数え直しになり \(O(N^2)\)。

型

先頭と最後に 1 つずつ余分な場所を作り（1-indexed で 0 と N+1）、そこに何もない範囲の値を入れておく。

操作何もない範囲の値
最大LLONG_MIN（どの値にも負ける）
最小LLONG_MAX（どの値にも勝つ）
和0
GCD0 (gcd(0, x) = x)
vector<ll> L(N + 2, 何もない値), R(N + 2, 何もない値);
for (int i = 1; i <= N; i++)  L[i] = op(L[i-1], A[i]);   // 前から
for (int i = N; i >= 1; i--)  R[i] = op(R[i+1], A[i]);   // 後ろから
for (int i = 1; i <= N; i++) {
    ll v = op(L[i-1], R[i+1]);   // i を除いた全体
    ans = max(ans, v);
}

練習問題