Overview

Since each operation adds \(+1\) to a “contiguous interval (at most 3 elements),” we use a difference array (imos method) to batch the additions, then apply them all at once at the end to determine the final brightness.

Analysis

A single light bulb replacement increases the brightness around streetlight \(B_j\), specifically in the range \([B_j-1,\, B_j+1]\) (ignoring out-of-bounds portions at the edges). Therefore, each operation can be rephrased as an “interval addition.”

Why the naive approach can be slow

Naively, for each operation we could: - Add \(+1\) to \(A_{B_j-1}\), \(A_{B_j}\), and \(A_{B_j+1}\) (if they exist)

This requires at most 3 updates per operation, so the time complexity is \(O(M)\), which actually fits within the time limit for this particular problem.

However, in competitive programming, operations are often extended to things like “add to an entire interval,” in which case naively updating every element in the interval leads to a worst case of \(O(NM)\), resulting in TLE. Since this problem can also be formulated as “interval additions,” it is safer to solve it using the versatile and efficient difference array (imos method).

How to solve it (key insight)

When repeatedly performing “add \(+1\) uniformly to interval \([l, r]\),” instead of updating the array each time, we can: - Add \(+1\) to diff[\(l\)] - Add \(-1\) to diff[\(r+1\)]

Then, by taking the prefix sum at the end, we can obtain the number of additions at each position all at once.

Algorithm

1. Prepare a difference array diff of length \(N+2\) (to simplify boundary handling).
2. For each operation with streetlight \(b=B_j\), determine the affected range as \(l=\max(1, b-1)\), \(r=\min(N, b+1)\).
3. Record the interval addition in the difference array:
   • diff[l] += 1
   • diff[r+1] -= 1
4. For \(i=1..N\), accumulate cur += diff[i] and perform A[i-1] += cur. Here, cur represents “how many times streetlight \(i\) was incremented by \(+1\).”

Concrete Example

For example, if \(N=5\) and the operations are \(b=1\) and \(b=4\): - The effect of \(b=1\) covers \([1,2]\) - The effect of \(b=4\) covers \([3,5]\)

The difference array updates are: - diff[1]+=1, diff[3]-=1 - diff[3]+=1, diff[6]-=1 (we allocate size \(N+2\) so we can access indices beyond \(N+1\))

Taking the prefix sum yields the number of additions at each position all at once.

Complexity

• Time complexity: \(O(N+M)\) (recording \(M\) operations + computing the prefix sum over \(N\) elements)
• Space complexity: \(O(N)\) (for the difference array)

Implementation Notes

• The affected interval must always be clamped with \(l=\max(1, b-1)\) and \(r=\min(N, b+1)\).

• Since we access diff[r+1], it is safe to make diff of length \(N+2\) (when \(r=N\), we use up to index r+1=N+1).

• Since the input can be up to \(2\times 10^5\), reading all input at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    A = [next(it) for _ in range(N)]
    diff = [0] * (N + 2)

    for _ in range(M):
        b = next(it)
        l = b - 1
        if l < 1:
            l = 1
        r = b + 1
        if r > N:
            r = N
        diff[l] += 1
        diff[r + 1] -= 1

    cur = 0
    for i in range(1, N + 1):
        cur += diff[i]
        A[i - 1] += cur

    sys.stdout.write(" ".join(map(str, A)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.