概要

数列の各区間に複数回の加算操作を行い、最終的な数列の状態を求める問題です。

考察

この問題では、最大で \(2 \times 10^5\) 個の要素と操作を行う可能性があるため、素直に各区間に対して毎回加算処理を行うと、最悪計算量が \(O(NM)\) となり、時間制限を超える可能性があります（TLE）。

例えば、各操作で区間 \([L_i, R_i]\) の全要素に \(1\) を足す処理をそのまま実行すると、1回の操作につき最大 \(N\) 回の更新が必要になり、全体で最大 \(2 \times 10^{10}\) 回の計算が必要になることがあります。

そこで、差分配列（いもす法）というテクニックを使います。これは、区間への一様加算を効率的に行うための前処理テクニックです。

具体的には、ある区間 \([L, R]\) に値 \(x\) を加える操作を、

• diff[L] += x
• diff[R+1] -= x

として記録しておきます。こうすることで、各操作が定数時間 \(O(1)\) で終わります。その後、累積和を取ることで元の配列を復元できます。

例：

例えば、\(N = 5\), 操作が \([1, 3]\) だったとします。

初期の差分配列：[0, 0, 0, 0, 0, 0] （サイズ \(N+1\)）

操作 [1, 3] → diff[1] += 1, diff[4] -= 1
→ [0, 1, 0, 0, -1, 0]

これに累積和を適用すると：[0, 1, 1, 1, 0, 0]
つまり、元の配列の添字 \(1\)〜\(3\) に \(1\) が加算されたことになります（0-indexedなら添字変換が必要）。

このようにして、区間更新を効率的に処理します。

アルゴリズム

1. 長さ \(N+1\) の差分配列 diff を用意する（0-indexedで扱いやすくするため）。
2. 各操作 \([L_i, R_i]\) に対して以下を行う：
   • diff[L_i - 1] += 1
   • diff[R_i] -= 1
3. diff の累積和を取り、元の配列を復元する。

計算量

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

実装のポイント

• 差分配列はサイズを \(N+1\) にしておくと、境界処理が楽になります。

• 最後に累積和を取る際に、current 変数を使って前の値を保持しながら更新していくと効率的です。

• 入力を高速に読み込むために sys.stdin.read を使用しています。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 差分配列を初期化
    diff = [0] * (N + 1)
    
    index = 2
    for _ in range(M):
        L = int(data[index])
        R = int(data[index + 1])
        index += 2
        
        diff[L - 1] += 1
        diff[R] -= 1
    
    # 差分配列から元の配列を構築
    result = []
    current = 0
    for i in range(N):
        current += diff[i]
        result.append(current)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

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