概要

各街灯の初期明るさに加えて、指定された位置の電球を交換することで周囲の明るさが増加する処理を行い、最終的な各街灯の明るさを求めます。

考察

この問題では、最大で \(2 \times 10^5\) 個の街灯と同数の操作があるため、素朴に毎回3つの街灯の明るさを直接更新していると、最悪ケースで \(3 \times 10^5 \times 10^5 = 6 \times 10^{10}\) 回の更新が必要になり、時間制限を超えてしまいます（TLE）。

そこで、「範囲に対して一定の値を加算する」という操作を効率的に処理するために imos法（いもすほう） を使います。imos法では、区間の始点に加算する値を足し、終点の次の位置からその値を引くことで、差分情報を記録します。その後、累積和を取ることで各区間への加算回数を高速に求めることができます。

この問題では、ある街灯 \(B_j\) を交換するたびに、区間 \([\max(1, B_j - 1), \min(N, B_j + 1)]\) のすべての街灯の明るさが1増えるので、imos法を適用できます。

アルゴリズム

1. 長さ \(N+1\) の差分配列 diff を用意します（1-indexedの扱いを楽にするため）。
2. 各操作 \(B_j\) に対して、影響を受ける区間 \([left, right]\) を求めます：
   • \(left = \max(1, B_j - 1)\)
   • \(right = \min(N, B_j + 1)\)
3. imos法により、diff[left - 1] += 1、diff[right] -= 1 を行います。
4. diff の累積和を取りながら、各街灯の最終的な明るさ \(A_i + \text{加算回数}\) を計算します。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 街灯のインデックスが1-originなので、配列アクセス時には適切に変換する必要があります。
• diff 配列のサイズを \(N+1\) にしておくことで、境界処理がシンプルになります。
• 最後に累積和を計算する際に、current_add 変数を使って効率よく処理しています。

## ソースコード

```python
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    A = list(map(int, data[2:2+N]))
    B = list(map(int, data[2+N:2+N+M]))
    
    # 差分更新用の配列（imos法）
    diff = [0] * (N + 1)
    
    # 各操作を差分として記録
    for b in B:
        left = max(1, b - 1)
        right = min(N, b + 1)
        diff[left - 1] += 1
        if right < N:
            diff[right] -= 1
            
    # 差分を累積和して各街灯への加算回数を得る
    current_add = 0
    result = []
    for i in range(N):
        current_add += diff[i]
        result.append(A[i] + current_add)
        
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。