概要

各操作で「連続した区間（最大で3個）」に \(+1\) されるので、差分配列（いもす法）でまとめて加算し、最後に一括で反映して最終の明るさを求めます。

考察

1回の電球交換で増えるのは街灯 \(B_j\) の周辺、つまり
\([B_j-1,\, B_j+1]\) の範囲（ただし端でははみ出す分を無視）です。
したがって、各操作は「区間加算」に言い換えられます。

素朴な方法が遅い理由

素朴には、各操作ごとに - \(A_{B_j-1}\), \(A_{B_j}\), \(A_{B_j+1}\) を（存在するなら）それぞれ \(+1\)

とすればよく、これは1操作あたり最大3回の更新なので計算量は \(O(M)\) で、実はこの問題設定だとそれでも間に合います。

しかし競技プログラミングでは、操作が「区間全体に加算」などに拡張されることが多く、その場合は素朴に区間の全要素を更新すると最悪 \(O(NM)\) となり TLE になります。今回も「区間加算」としてまとめて処理できる形なので、汎用的で高速な差分配列（いもす法）で解くのが安全です。

どう解決するか（重要な気づき）

「区間 \([l, r]\) に一様に \(+1\)」を何度も行う場合は、配列そのものを毎回更新せず、 - diff[\(l\)] に \(+1\) - diff[\(r+1\)] に \(-1\)

と記録しておき、最後に prefix sum（累積和）を取ると各位置の加算回数が一度に求まります。

アルゴリズム

1. 差分配列 diff を長さ \(N+2\) で用意（境界処理を簡単にするため）。
2. 各操作で街灯 \(b=B_j\) が与えられたら、影響範囲を
   \(l=\max(1, b-1)\), \(r=\min(N, b+1)\) とする。
3. 区間加算の差分記録として
   • diff[l] += 1
   • diff[r+1] -= 1
4. \(i=1..N\) について cur += diff[i] と累積し、A[i-1] += cur を行う。
   cur が「街灯 \(i\) が何回 \(+1\) されたか」を表す。

具体例

例えば \(N=5\)、操作が \(b=1\) と \(b=4\) の2回なら、 - \(b=1\) の影響は \([1,2]\) - \(b=4\) の影響は \([3,5]\)

差分は - diff[1]+=1, diff[3]-=1 - diff[3]+=1, diff[6]-=1（\(N+1\) 以降まで置けるように \(N+2\) を確保）

累積和を取ると各位置の加算回数が一気に求まります。

計算量

• 時間計算量: \(O(N+M)\)（操作の記録 \(M\) 回＋累積和 \(N\) 回）
• 空間計算量: \(O(N)\)（差分配列）

実装のポイント

• 影響区間は必ず \(l=\max(1, b-1)\)、\(r=\min(N, b+1)\) のように端を丸める。

• diff[r+1] にアクセスするため、diff は長さ \(N+2\) にしておくと安全（\(r=N\) のとき r+1=N+1 まで使う）。

• 入力が最大 \(2\times 10^5\) なので、sys.stdin.buffer.read() でまとめて読むと高速です。

  ソースコード

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

---

この解説は gpt-5.2-high によって生成されました。