Overview

Create an array \(V\) by replacing only the broken sensor values with their estimated values, then compute the fluctuation by summing the absolute differences of adjacent elements \(|V_{i+1}-V_i|\) from left to right.

Analysis

What we need in this problem is only the final value sequence \(V_1,\dots,V_N\). The final value \(V_i\) for each sensor \(i\) is uniquely determined as:

• \(A_i\) if it is not broken
• The corresponding estimated value \(C_j\) if it is broken

The key observations are the following two points:

1. The fluctuation is the sum of adjacent differences, so it can be computed in a single left-to-right pass
   \(\sum_{i=1}^{N-1}|V_{i+1}-V_i|\) can be calculated by simply adding up the differences sequentially from \(i=1\) once \(V\) is determined.

2. The broken sensor indices \(B_j\) do not need to be in ascending order
   We just need to perform the assignment \(V[B_j]=C_j\) for each one, and the order does not matter (since all \(B_j\) are distinct by the constraints, there are no overwrite conflicts).

A naive approach like “recalculating the affected fluctuation for each broken sensor” would require scanning the entire array multiple times in the worst case, resulting in \(O(NK)\) which is too slow.
This problem can be solved in \(O(N+K)\) by replacing once and summing once.

(Example)
When \(A=[1,5,3,10]\), broken: \(B=[2,4]\), estimated: \(C=[7,6]\)
After replacement: \(V=[1,7,3,6]\)
The fluctuation is \(|7-1|+|3-7|+|6-3|=6+4+3=13\).

Algorithm

1. Prepare array \(V\) as a copy of \(A\).
2. For each \(j=1..K\), replace \(V_{B_j}\) with \(C_j\) (in implementation, use \(V[B_j-1]=C_j\) due to 0-indexing).
3. For \(i=1..N-1\), accumulate \(|V_{i+1}-V_i|\) to obtain the answer.

Complexity

• Time complexity: \(O(N+K)\) (\(K\) replacements and \(N-1\) difference additions)
• Space complexity: \(O(N)\) (to store array \(V\))

Implementation Notes

• Be careful with index offsets: The input sensor indices \(B_j\) are 1-indexed, while Python lists are 0-indexed, so use V[B[j]-1] = C[j].

• \(B\) does not need to be sorted: Simply assigning the values produces the correct \(V\) (since all \(B_j\) are distinct).

• Fast input: Since \(N\) can be up to \(2\times 10^5\), using sys.stdin.buffer.read() to read all input at once is a stable and fast approach.

  Source Code

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()

This editorial was generated by gpt-5.2-high.