概要

故障したセンサーの値だけを推定値に置き換えた配列 \(V\) を作り、隣り合う要素の差の絶対値 \(|V_{i+1}-V_i|\) を左から順に合計して変動量を求めます。

考察

この問題で必要なのは最終的な値列 \(V_1,\dots,V_N\) のみです。各センサー \(i\) の最終値 \(V_i\) は

• 故障していなければ \(A_i\)
• 故障していれば対応する推定値 \(C_j\)

で一意に定まります。

重要な観察は次の2点です。

1. 変動量は隣接差の総和なので、左から1回なめれば計算できる
   \(\sum_{i=1}^{N-1}|V_{i+1}-V_i|\) は、\(V\) が決まれば \(i=1\) から順に差を足すだけです。

2. 故障センサーの番号 \(B_j\) は昇順でなくても問題ない
   \(V[B_j]=C_j\) の代入をそれぞれ行えばよく、順序は関係ありません（制約より \(B_j\) はすべて異なるので上書き競合もありません）。

素朴に「各故障センサーごとに影響する変動量を都度計算し直す」ようなことをすると、最悪で何度も全体を走査してしまい \(O(NK)\) になって間に合いません。
本問題は 一度だけ置き換えて、一度だけ合計する ことで \(O(N+K)\) で解けます。

（例）
\(A=[1,5,3,10]\), 故障: \(B=[2,4]\), 推定: \(C=[7,6]\) のとき
置換後 \(V=[1,7,3,6]\)
変動量は \(|7-1|+|3-7|+|6-3|=6+4+3=13\) です。

アルゴリズム

1. 配列 \(V\) を \(A\) のコピーとして用意する。
2. 各 \(j=1..K\) について、\(V_{B_j}\) を \(C_j\) に置き換える（実装では 0-index のため \(V[B_j-1]=C_j\)）。
3. \(i=1..N-1\) について \(|V_{i+1}-V_i|\) を加算して答えを得る。

計算量

• 時間計算量: \(O(N+K)\)（置換が \(K\) 回、差分の合計が \(N-1\) 回）
• 空間計算量: \(O(N)\)（配列 \(V\) を保持するため）

実装のポイント

• 添字のずれに注意: 入力のセンサー番号 \(B_j\) は 1-index、Python のリストは 0-index なので V[B[j]-1] = C[j] とします。

• \(B\) が未ソートでもOK: そのまま代入すれば正しい \(V\) が作れます（\(B_j\) は相異なる）。

• 高速入力: \(N\) が最大 \(2\times 10^5\) なので、sys.stdin.buffer.read() でまとめて読み取る実装は安定して高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    K = next(it)

    A = [next(it) for _ in range(N)]
    B = [next(it) for _ in range(K)]
    C = [next(it) for _ in range(K)]

    V = A[:]  # copy
    for j in range(K):
        V[B[j] - 1] = C[j]

    ans = 0
    prev = V[0]
    for i in range(1, N):
        cur = V[i]
        ans += abs(cur - prev)
        prev = cur

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。