Overview

There are \(N\) streetlights, and when the bulb of a specific streetlight is replaced, the brightness of that streetlight itself and its two adjacent streetlights each increases by \(1\). The problem asks to find the final brightness of each streetlight after \(M\) replacement operations.

Analysis

The key point of this problem is to organize “which replacement operations cause the brightness of a given streetlight \(i\) to increase.”

The brightness of streetlight \(i\) increases when the bulb of any of the following streetlights is replaced: 1. When the bulb of streetlight \(i-1\) is replaced (light reaches \(i\), which is its right neighbor) 2. When the bulb of streetlight \(i\) is replaced (itself) 3. When the bulb of streetlight \(i+1\) is replaced (light reaches \(i\), which is its left neighbor)

Therefore, the brightness of streetlight \(i\) after all operations is the following sum: $\((\text{initial brightness } A_i) + (\text{number of times streetlight } i-1 \text{ was replaced}) + (\text{number of times streetlight } i \text{ was replaced}) + (\text{number of times streetlight } i+1 \text{ was replaced})\)$

A naive simulation approach would be to “directly update the brightness of the 3 adjacent streetlights each time a replacement operation \(B_j\) occurs.” In this case, each operation updates at most 3 positions, so the overall time complexity is \(O(M + N)\), which is sufficiently fast for the given constraints (\(N, M \leq 2 \times 10^5\)).

In the provided code, a more organized approach is used: first count how many times each streetlight was replaced, then compute the final brightness of each streetlight all at once.

Algorithm

The solution follows these steps:

1. Counting replacements: Prepare an array count of length \(N+2\) (managed with 1-indexing, allocated slightly larger to simplify boundary handling). Scan through the given \(B_1, B_2, \ldots, B_M\) and increment count[B_j] by \(1\) for each.

2. Computing final brightness: For each streetlight \(i = 1, 2, \ldots, N\), compute: $\(\text{ans}_i = A_i + \text{count}[i-1] + \text{count}[i] + \text{count}[i+1]\)\( Here, for streetlight \)1\( we reference `count[0]`, and for streetlight \)N\( we reference `count[N+1]`, but since these remain \)0$, the computation is correct without any conditional branching.

3. Output: Output the computed results separated by spaces.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\), counting replacements takes \(O(M)\), and computing final brightness takes \(O(N)\).
• Space complexity: \(O(N + M)\)
  • Required for storing input data, the brightness array \(A\), and the replacement count array count.

Implementation Notes

• Fast I/O: In Python, when \(N, M\) are on the order of \(2 \times 10^5\), repeatedly calling the standard input() may result in a Time Limit Exceeded (TLE). By using sys.stdin.read().split() to read all input at once, we achieve faster I/O.

• Sentinel (simplifying boundary conditions): By setting the size of the count array to \(N+2\), accessing the left neighbor of streetlight \(1\) (index 0) or the right neighbor of streetlight \(N\) (index \(N+1\)) does not cause an error, and these positions are treated as having value \(0\). This eliminates the need for if statements to handle boundary cases.

  Source Code

import sys

def solve():
    # 読み込みの高速化のため、すべての入力を一括で取得して分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 街灯の数, M: 電球交換の回数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # A: 各街灯の初期の明るさ（0-indexedのリストとして格納）
    # input_data[2] から input_data[2+N-1] までが A_1 から A_N に対応
    A = list(map(int, input_data[2 : 2 + N]))
    
    # count[i]: 街灯 i の電球が交換された回数
    # 1-indexedで管理するため、サイズを N+2 とし、境界条件（0 と N+1）もカバーします
    count = [0] * (N + 2)
    # input_data[2+N] から input_data[2+N+M-1] までが B_1 から B_M に対応
    for i in range(2 + N, 2 + N + M):
        b = int(input_data[i])
        count[b] += 1
        
    # すべての作業が終わった後の各街灯の明るさを計算します
    # 街灯 i の明るさは、初期の明るさ A_i に加え、
    # 街灯 i-1, i, i+1 の電球が交換された回数の合計分だけ増加します
    ans = [None] * N
    for i in range(1, N + 1):
        # A[i-1] は街灯 i の初期の明るさ
        # count[i-1], count[i], count[i+1] はそれぞれ隣接および自身の電球交換回数
        # count[0] と count[N+1] は常に 0 であるため、端の街灯も正しく計算されます
        final_brightness = A[i-1] + count[i-1] + count[i] + count[i+1]
        ans[i-1] = str(final_brightness)
        
    # 結果をスペース区切りで1行に出力します
    sys.stdout.write(" ".join(ans) + "\n")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.