Overview

This problem asks you to replace faulty sensor values with estimated values, then compute the sum of absolute differences between adjacent sensor values (the total variation).

Analysis

In this problem, you are given the original sensor measurements \(A\), and you need to consider a new sequence \(V\) where only the faulty sensor values are replaced by Aoki’s estimated values \(C\).

Since the total variation is the sum of absolute differences between adjacent elements, we need to compute:

\[ \sum_{i=1}^{N-1} |V_{i+1} - V_i| \]

A straightforward approach is to first construct \(V\), then sum up the absolute differences of adjacent terms. At this point, we need to efficiently determine which sensors are faulty. If we naively search through the list \(B\) each time, it takes \(O(NK)\) in the worst case, and since the constraints are \(N, K \leq 200000\), this would result in TLE.

To solve this, we use a dictionary (hash map) that maps faulty sensor numbers (1-indexed) to their corresponding estimated values. This allows us to determine whether each sensor is faulty in \(O(1)\) time.

Algorithm

1. Read input efficiently (using sys.stdin.read).
2. Create a dictionary faulty with faulty sensor numbers (0-indexed) as keys and estimated values as values.
3. For each sensor, construct the sequence \(V\) using the estimated value if the sensor is faulty, or the normal value otherwise.
4. Sum the absolute differences of adjacent elements to compute the total variation.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Sensor numbers are given as 1-indexed, so they need to be converted to 0-indexed for internal processing (B[j] - 1).

• Using linear search through a list for faulty sensor detection is slow, so use a dictionary (Python’s dict) to enable \(O(1)\) access.

• Using fast input processing ensures the solution can handle large inputs.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    
    A = list(map(int, data[2:2+N]))
    
    B = list(map(int, data[2+N:2+N+K]))
    C = list(map(int, data[2+N+K:2+N+2*K]))
    
    # 故障センサーのインデックスと推定値のマッピング（0-indexed）
    faulty = {}
    for i in range(K):
        faulty[B[i] - 1] = C[i]
    
    # 補完されたデータ列 V を作成
    V = []
    for i in range(N):
        if i in faulty:
            V.append(faulty[i])
        else:
            V.append(A[i])
    
    # 変動量を計算
    total = 0
    for i in range(N - 1):
        total += abs(V[i + 1] - V[i])
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.