概要

各区間 \([L,R]\) に対して「その区間の全要素を \(1\) 減らす」操作が \(Q\) 回行われるので、各スマートフォンが合計で何回減らされるかを高速に数え、最後に \(S_i-\text{回数}\) を \(0\) 未満にならないように丸めて出力します。

考察

重要な気づき

各スマートフォン \(i\) の最終残量は、結局 - 「イベントがスマホ \(i\) を何回含むか」を \(c_i\) とすると - 最終的に \(S_i' = \max(0,\, S_i - c_i)\)

となります。イベントの順番や途中で \(0\) になったかどうかは、最終結果に対しては \(S_i\) から合計減少回数を引いて \(0\) で下限を取る だけで良い、という点がポイントです（\(0\) 以下にはならないので）。

素朴解がなぜ遅いか

各イベントごとに区間 \([L,R]\) を全部走査して \(1\) ずつ減らすと、最悪で - 1回のイベントで \(O(N)\) - それが \(Q\) 回で \(O(NQ)\)

となり、\(N,Q \le 2\times 10^5\) では間に合いません。

どう解決するか

必要なのは「各位置が区間更新に何回含まれたか」だけなので、区間加算を高速に処理できる 差分配列（いもす法） を使い、各 \(c_i\) を \(O(N+Q)\) で求めます。

アルゴリズム

差分配列 diff を長さ \(N+1\) で用意し、各イベント \([L,R]\)（1-indexed, 両端含む）について次を行います（0-indexedに直して処理）：

• \(L' = L-1\) として
  diff[L'] += 1
• 区間の右端の「次」から影響を打ち消すために、\(R\) が \(N\) 未満なら
  diff[R] -= 1
  （ここで R は 1-indexed の右端なので、0-indexed では「右端の次」の位置に対応します）

その後、左から順に累積和 cur を取り、 - cur += diff[i] により \(c_i = cur\) を得る - 最終値は S[i] = max(0, S[i] - cur) とする

具体例

\(N=5\)、イベントが \([2,4]\) の1回だけだとします。 - diff[1] += 1（2番目から減る） - diff[4] -= 1（4番目の次=5番目からは減らない）

diff の累積和は [0,1,1,1,0] になり、2〜4番目だけ1回減ることが分かります。

計算量

• 時間計算量: \(O(N+Q)\)（差分更新が \(Q\) 回、累積和が \(N\) 回）
• 空間計算量: \(O(N)\)（差分配列）

実装のポイント

• 入力の \([L,R]\) は 1-indexed なので、左端だけ L -= 1 して 0-indexed に合わせる。

• diff[R] -= 1 は \(R < N\) のときだけ 行う（範囲外アクセス防止）。

• 最終値は max(0, ...) で \(0\) 未満にならないようにする。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(int, input().split()))
    diff = [0] * (N + 1)

    for _ in range(Q):
        L, R = map(int, input().split())
        L -= 1
        diff[L] += 1
        if R < N:
            diff[R] -= 1

    cur = 0
    for i in range(N):
        cur += diff[i]
        v = S[i] - cur
        S[i] = v if v > 0 else 0

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

if __name__ == "__main__":
    main()

---

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