概要

\(N\) 個の要素（初期値 \(0\)）に対して、指定された区間 \([L, R]\) に \(1\) を加算する操作を \(M\) 回行い、最終的な数列の状態を求める問題です。

考察

素直なアプローチ

各操作において、数列の \(L\) 番目から \(R\) 番目までを一つずつループで加算していく方法が考えられます。 しかし、この方法では 1 回の操作に最大で \(O(N)\) の時間がかかります。操作は \(M\) 回行われるため、全体の計算量は \(O(NM)\) となります。 本問題の制約では \(N, M \leq 2 \times 10^5\) であるため、\(N \times M \approx 4 \times 10^{10}\) となり、一般的な実行時間制限（2秒程度）を大幅に超えてしまい、TLE（実行時間制限超過）となります。

効率的なアプローチ

「区間全体に一律に加算する」という操作を効率化するために、「いもす法（差分配列）」という手法を用います。 この手法では、区間の全要素を更新する代わりに、「区間の開始地点」と「区間の終了地点の直後」の 2 箇所だけを記録します。これにより、1 回の操作を \(O(1)\) で処理できるようになります。

アルゴリズム

いもす法の手順

1. 差分配列の準備: 長さ \(N+1\)（または余裕を持って \(N+2\)）の配列 diff を用意し、すべて \(0\) で初期化します。
2. 加算予約（クエリ処理）: 各操作 \([L, R]\) に対して以下を行います。
   • diff[L] に \(1\) を加える（ここから値が \(1\) 増えるという印）。
   • diff[R + 1] から \(1\) を引く（ここから値が \(1\) 減る、つまり増分が相殺されるという印）。
3. 累積和の計算: 左から順に diff 配列の累積和をとります。
   • \(i\) 番目の要素の最終的な値は、\(\sum_{k=1}^{i} diff[k]\) となります。

具体例

\(N=5\) で、区間 \([2, 4]\) に \(1\) を加算する場合： - diff[2] += 1 - diff[5] -= 1 （\(R+1 = 5\)） - diff 配列の状態: [0, 0, 1, 0, 0, -1] - 累積和をとる: [0, 0, 1, 1, 1, 0] - 結果として、2番目から4番目までが \(1\) になります。

計算量

• 時間計算量: \(O(N + M)\)
  • \(M\) 回のクエリ処理に \(O(M)\)、最後の累積和の計算に \(O(N)\) かかります。
  • \(N, M = 2 \times 10^5\) の場合、約 \(4 \times 10^5\) 回の操作で済むため、十分に高速です。
• 空間計算量: \(O(N)\)
  • 数列の状態を保持するための配列 diff および結果用の配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python では input() よりも sys.stdin.read().split() などを用いて一括で入力を読み込む方が実行時間を短縮できます。

• 配列のサイズ: diff[R + 1] にアクセスするため、配列のサイズは \(N+1\) 以上確保する必要があります。

• インデックスの扱い: 問題文は \(1\)-indexed（1始まり）ですが、Python のリストは \(0\)-indexed です。コードでは diff を大きめに確保することで \(1\)-indexed のまま扱い、出力時に調整しています。

  ソースコード

import sys

def solve():
    # 標準入力から全てのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # いもす法（累積和）を用いるための差分配列を用意
    # インデックスは1からNまでをカバーし、R+1の操作のためにサイズN+2を確保
    diff = [0] * (N + 2)
    
    # 各クエリに対して差分配列を更新
    for i in range(M):
        L = int(input_data[2 + 2 * i])
        R = int(input_data[3 + 2 * i])
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を計算して各要素の最終的な値を求める
    ans = [0] * N
    current_val = 0
    for i in range(1, N + 1):
        current_val += diff[i]
        ans[i - 1] = current_val
    
    # 結果をスペース区切りで出力
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == '__main__':
    solve()

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