概要

\(N\) 台のスマートフォンがあり、それぞれに初期バッテリー残量が設定されています。
\(Q\) 個の通知イベントがあり、各イベントではある区間のスマートフォンのバッテリーを1減らします（ただし0未満にはなりません）。
すべてのイベント後に各スマートフォンのバッテリー残量を求めます。

考察

この問題は、単純に考えると各イベントごとに区間 \([L, R]\) のスマートフォンのバッテリーを1ずつ減らす処理を行おうとするかもしれませんが、そのような素朴な実装では時間計算量が \(O(Q \times N)\) となり、制約 \(N, Q \leq 2 \times 10^5\) のもとでは非常に大きな計算量となり、TLE（時間超過）になります。

そこで、「区間に対して一定の値を加える」という操作を効率的に処理するために、差分配列（いもす法）を用います。
差分配列を使うことで、区間更新を \(O(1)\) で行い、最後に累積和を取ることで各要素への加算量を高速に求めることができます。

具体的には、イベントごとに区間 \([L, R]\) に1を加算する代わりに、差分配列の位置 \(L\) に \(+1\)、位置 \(R+1\) に \(-1\) を記録します。その後、累積和を取ることで各スマートフォンに対する減少量が求まります。

最後に、初期バッテリー量からその減少量を引き、0以上にクリップすれば答えが得られます。

アルゴリズム

1. 入力を高速に読み込む（sys.stdin.read を使用）。
2. 差分配列 diff をサイズ \(N+1\) で用意する（端処理のため1要素多く）。
3. 各イベントに対して：
   • 区間 \([L, R]\) に対して、diff[L] += 1、diff[R+1] -= 1 を行う（0-indexedに変換）。
4. 差分配列の累積和を取り、各スマートフォンに対する減少量 decrements を求める。
5. 各スマートフォンの初期バッテリー量から減少量を引き、0以上にクリップした値を出力する。

計算量

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

実装のポイント

• インデックスを0-basedに変換すること（入力は1-based）。
• 差分配列のサイズは \(N+1\) にして、範囲外アクセスを防ぐ。
• 最終結果は max(0, S[i] - decrements[i]) として負にならないようにする。
• 高速な入力処理（sys.stdin.read）を使用することで、大量の入力にも対応できる。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    
    S = list(map(int, data[2:2+N]))
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    index = 2 + N
    for _ in range(Q):
        L = int(data[index]) - 1   # 0-indexedにする
        R = int(data[index+1]) - 1
        diff[L] += 1
        diff[R+1] -= 1
        index += 2
    
    # 差分配列を累積和して、各要素への減少量を求める
    decrements = list(accumulate(diff[:-1]))
    
    # 各スマートフォンの最終バッテリー量を計算
    result = [max(0, S[i] - decrements[i]) for i in range(N)]
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

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