概要

数列に対して複数の区間加算操作を行い、最終的な各要素の値を求める問題です。

考察

素朴なアプローチとして、各操作ごとに指定された区間 \([L_i, R_i]\) のすべての要素に1を加算する方法が考えられます。しかし、\(N\) と \(M\) が最大で \(2 \times 10^5\) になるため、各操作で最大 \(2 \times 10^5\) 個の要素を更新すると、最悪ケースでは \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\) 回の操作が必要となり、時間制限に間に合いません。

この問題を効率的に解くには、区間加算を定数時間で処理できる「いもす法（Imos法）」と呼ばれる手法を使用します。いもす法では、各操作を区間の開始位置と終了位置の次の位置にマークを付けることで、最終的に1回の走査で全ての要素の値を計算できます。

アルゴリズム

いもす法の手順は以下の通りです：

1. 長さ \(N+2\) の配列 diff を0で初期化します（インデックスを1ベースで扱うため、+2しています）。
2. 各操作 \((L_i, R_i)\) に対して：
   • diff[L_i] に +1 する
   • diff[R_i + 1] に -1 する
3. 配列 diff の先頭から累積和を計算します。この累積和が各要素の最終的な値になります。

具体例で説明します。\(N=5\), \(M=2\) で、操作が \((1, 3)\) と \((2, 4)\) の場合： - 操作1: diff[1] += 1, diff[4] -= 1 - 操作2: diff[2] += 1, diff[5] -= 1 - 累積和を計算： - index1: 0 + 1 = 1 - index2: 1 + 1 = 2 - index3: 2 + 0 = 2 - index4: 2 - 1 = 1 - index5: 1 - 1 = 0 - 結果: [1, 2, 2, 1, 0]

計算量

• 時間計算量: \(O(N + M)\)
  • 各操作の処理に \(O(1)\)、累積和の計算に \(O(N)\) かかるため
• 空間計算量: \(O(N)\)
  • 差分配列に \(O(N)\) のメモリを使用するため

実装のポイント

• 配列のインデックスを1ベースで扱うため、配列のサイズを \(N+2\) に確保しています（\(R_i+1\) が \(N+1\) までアクセス可能になるため）

• 入力データを一括で読み込むことで、高速な処理を実現しています

• 累積和を計算する際は、現在の値を保持する変数 current を使い、各位置で差分配列の値を加算していきます

• 出力形式に注意し、スペース区切りで数値を文字列に変換して出力します

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    
    diff = [0] * (n + 2)
    
    index = 2
    for _ in range(m):
        l = int(data[index])
        r = int(data[index + 1])
        index += 2
        diff[l] += 1
        diff[r + 1] -= 1
    
    current = 0
    result = []
    for i in range(1, n + 1):
        current += diff[i]
        result.append(str(current))
    
    print(" ".join(result))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。