概要

\(N\) 台のスマートフォンの初期バッテリー残量に対し、指定された範囲 \([L, R]\) の残量を \(1\) 減らす操作を \(Q\) 回行った後の最終的な残量を求める問題です。ただし、残量は \(0\) 未満にはなりません。

考察

素朴なアプローチ

各通知イベントごとに、範囲 \([L, R]\) に含まれるすべてのスマートフォンの値を \(1\) ずつ減らす方法が考えられます。しかし、この方法では \(1\) 回のイベントにつき最大で \(N\) 回の更新が必要になります。 最悪の場合の計算量は \(O(NQ)\) となり、今回の制約（\(N, Q \leq 2 \times 10^5\)）では \(4 \times 10^{10}\) 回程度の計算が必要になるため、実行時間制限に間に合いません（TLEとなります）。

効率的なアプローチの検討

この問題の重要なポイントは以下の2点です。 1. 減少量は常に \(1\) である：各イベントで減る量は固定です。 2. 「\(0\) 未満にならない」の処理：各イベントごとに \(0\) かどうかを判定して更新しなくても、最終的な減少回数の合計がわかれば、最後にまとめて「初期値 \(-\) 減少回数」を計算し、結果がマイナスなら \(0\) とすることで正しい答えが得られます。

したがって、この問題は「各スマートフォンが合計で何回の通知イベントに含まれたか」を高速に数え上げる問題に言い換えられます。

いもす法（imos法）の利用

特定の範囲 \([L, R]\) に対して一括で加算（今回は通知回数のカウント）を行う場合、「いもす法（imos法）」というアルゴリズムが非常に有効です。 - 長さ \(N+1\) の差分配列 diff を用意します。 - 範囲 \([L, R]\) に \(1\) を加える操作を、diff[L] += 1 と diff[R+1] -= 1 という 2 点の更新に置き換えます。 - すべてのクエリを処理した後、左から累積和をとることで、各地点の最終的な加算合計（通知回数）が \(O(N+Q)\) で求められます。

アルゴリズム

1. 長さ \(N+2\) の配列 diff を \(0\) で初期化します。
2. \(Q\) 個の通知イベント \([L_i, R_i]\) について、以下を行います：
   • diff[L_i] += 1
   • diff[R_i + 1] -= 1
3. 変数 current_events（現在の累積和）を \(0\) で初期化し、スマートフォンの番号 \(i = 1\) から \(N\) まで順番に以下を繰り返します：
   • current_events += diff[i]
   • \(i\) 番目のスマートフォンの最終残量を \(\max(0, S_i - current\_events)\) として計算します。
4. 計算した結果をすべて出力します。

計算量

• 時間計算量: \(O(N + Q)\)
  • 入力の読み込みに \(O(N + Q)\)、いもす法の加算操作に \(O(Q)\)、累積和の計算と最終的な残量の算出に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 初期残量を保持する配列と、いもす法のための差分配列で \(O(N)\) のメモリを使用します。

実装のポイント

• 大量の入出力: Python の場合、input() や print() を繰り返すと時間がかかるため、sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで高速化を図っています。

• インデックスの扱い: 問題文は \(1\)-indexed（1番目から始まる）ですが、プログラム内での配列の扱いや範囲外参照（R+1）に注意して実装する必要があります。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します
    # 大量の入力を処理するため、sys.stdin.read().split() を使用します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # スマートフォンの初期バッテリー残量
    S = list(map(int, input_data[2:N+2]))
    
    # いもす法（imos法）を用いて、各スマートフォンが何回の通知イベントに含まれるかを計算します
    # diff配列は、各インデックスでの変化量を記録します
    diff = [0] * (N + 2)
    
    # 通知イベントの読み込みと差分配列の更新
    idx = N + 2
    for _ in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        diff[L] += 1
        diff[R+1] -= 1
        idx += 2
        
    # 各スマートフォンの最終的なバッテリー残量を計算します
    # 各イベントで減少する量は 1 であり、0 未満にはならないため、
    # 最終的な減少量は「カバーされたイベントの総数」と「初期残量」の小さい方になります
    ans = [0] * N
    current_events = 0
    for i in range(N):
        # 累積和をとることで、i番目のスマートフォンがカバーされた回数を求めます
        current_events += diff[i+1]
        
        # 残量 = 初期値 - 通知回数（ただし 0 未満にはならない）
        res = S[i] - current_events
        if res < 0:
            res = 0
        ans[i] = res
        
    # 結果をスペース区切りで出力します
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == "__main__":
    main()

---

この解説は gemini-3-flash-preview によって生成されました。