Overview

This problem involves simulating brightness changes from streetlight bulb replacements. Each replacement operation increases the brightness of the target streetlight and its two neighbors by 1 each, so we need to efficiently calculate the final brightness of each streetlight.

Analysis

Understanding the Problem

When replacing the bulb of streetlight \(i\), the brightness of streetlights \(i-1\), \(i\), and \(i+1\) each increase by 1. For example, with \(N=5\) streetlights, if we replace the bulb of streetlight 3: - Streetlight 2’s brightness +1 - Streetlight 3’s brightness +1 - Streetlight 4’s brightness +1

When replacing bulbs at the end streetlights (streetlight 1 or streetlight N), non-existent streetlights are ignored.

Naive Approach

A straightforward method is to directly add to the brightness of the target streetlight and its neighbors in an array for each replacement operation.

Each operation updates at most 3 positions → O(M) operations results in O(3M) = O(M)

Since \(M \leq 2 \times 10^5\) in this problem, the naive approach is sufficiently fast.

Key Insights

• We just need to count “how many times each streetlight’s brightness is increased”
• The order of replacement operations doesn’t affect the result (addition is order-independent)
• Final brightness = Initial brightness \(A_i\) + number of times that streetlight was increased

Algorithm

1. Prepare Count Array: Create an array count to record the number of additions to each streetlight

2. Process Replacement Operations: For each replacement operation \(B_j\):

   • Increment count[B_j] by 1 (itself)
   • Increment count[B_j - 1] by 1 (left neighbor, if it exists)
   • Increment count[B_j + 1] by 1 (right neighbor, if it exists)

3. Calculate Final Result: For each streetlight \(i\), final brightness = \(A_i\) + count[i]

Concrete Example

For \(N=4\), \(M=2\), \(A = [1, 2, 3, 4]\), \(B = [2, 3]\):

Operation	Affected Streetlights
\(B_1 = 2\)	Streetlights 1, 2, 3
\(B_2 = 3\)	Streetlights 2, 3, 4

Count result: count = [1, 2, 2, 1]

Final brightness: \([1+1, 2+2, 3+2, 4+1] = [2, 4, 5, 5]\)

Complexity

• Time Complexity: \(O(N + M)\)
  • Array initialization: \(O(N)\)
  • Processing \(M\) replacement operations: \(O(M)\)
  • Computing results: \(O(N)\)
• Space Complexity: \(O(N)\)
  • Count array and result array: \(O(N)\)

Implementation Notes

1. Index Management:

   • In the problem statement, streetlights are numbered starting from 1 (1-indexed)
   • Python arrays start from 0 (0-indexed)
   • Use count array as 1-indexed, while keeping A array as 0-indexed

2. Preventing Out-of-Bounds Access:

   • Setting the size of count array to N + 2 allows for concise handling of edge cases
   • Alternatively, explicitly check boundaries with if b - 1 >= 1 or if b + 1 <= N

3. Handling Large Numbers:

   • \(A_i\) can be up to \(10^9\), and \(M\) additions can increase values by at most \(3M\)
   • In Python, there’s no need to worry about integer overflow

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # Count the number of additions to each streetlight
    count = [0] * (N + 2)  # Used as 1-indexed, +2 to prevent out-of-bounds access
    
    for b in B:
        # Replacing bulb of streetlight b increases brightness of b-1, b, b+1 by 1
        count[b] += 1  # Streetlight b itself
        if b - 1 >= 1:
            count[b - 1] += 1  # Left neighbor
        if b + 1 <= N:
            count[b + 1] += 1  # Right neighbor
    
    # Calculate results
    result = []
    for i in range(N):
        result.append(A[i] + count[i + 1])  # A is 0-indexed, count is 1-indexed
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.5opus.