概要

長さ \(N\) の数列（初期値すべて \(0\)）に対して、\(M\) 回の区間加算（指定区間の全要素に \(+1\)）を行った後の数列を求める問題です。いもす法（差分配列） を使うことで効率的に解けます。

考察

素朴なアプローチとその問題点

最も単純な方法は、各操作ごとに \(L_i\) から \(R_i\) までのすべての要素に \(1\) を加算することです。しかし、1回の操作で最大 \(N\) 個の要素を更新するため、\(M\) 回の操作全体で最悪 \(O(N \times M)\) の計算量になります。\(N, M\) がともに最大 \(2 \times 10^5\) なので、\(4 \times 10^{10}\) 回の演算となり、制限時間内に間に合いません（TLE）。

重要な気づき

区間全体に同じ値を加算する操作は、差分配列（いもす法） を使うと \(O(1)\) で表現できます。区間 \([L, R]\) への \(+1\) は、差分配列上で「位置 \(L\) に \(+1\)」「位置 \(R+1\) に \(-1\)」の2箇所を更新するだけで済みます。すべての操作を記録した後に、差分配列の累積和を取れば元の数列が復元できます。

アルゴリズム

いもす法の手順

1. 差分配列 diff を用意する（長さ \(N+1\)、初期値 \(0\)）
2. 各操作を差分配列に記録する: 操作 \([L_i, R_i]\) に対し、
   • diff[L_i - 1] += 1（0-indexed で位置 \(L_i - 1\)）
   • diff[R_i] -= 1（0-indexed で位置 \(R_i\)、つまり区間の右端の次）
3. 累積和を取る: diff[i] += diff[i-1]（\(i = 1, 2, \ldots, N-1\)）
4. diff[0] から diff[N-1] が答え

具体例

\(N = 5\), \(M = 2\)、操作が \([2, 4]\) と \([1, 3]\) の場合：

操作	diff[0]	diff[1]	diff[2]	diff[3]	diff[4]
初期	0	0	0	0	0
\([2,4]\): diff[1]+=1, diff[4]-=1	0	1	0	0	-1
\([1,3]\): diff[0]+=1, diff[3]-=1	1	1	0	-1	-1

累積和を取ると：

i	0	1	2	3	4
値	1	2	2	1	0

答えは 1 2 2 1 0 となり、確かに正しい結果です。

計算量

• 時間計算量: \(O(N + M)\)（差分配列への記録が \(O(M)\)、累積和の計算が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列の分）

実装のポイント

• 問題文は 1-indexed（番号が \(1\) から \(N\)）ですが、配列は 0-indexed で管理しているため、\(L_i\) を L_i - 1 に変換しています。

• 差分配列の「\(-1\) を入れる位置」が配列の範囲外にならないよう、if R < N のガード条件を入れています。\(R = N\) の場合は配列末尾までの加算なので、\(-1\) を入れる必要がありません。

• sys.stdin.buffer.read() で入力を一括読み込みすることで、Python でも高速に入力を処理しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    diff = [0] * (N + 1)
    for _ in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        diff[L - 1] += 1
        if R < N:
            diff[R] -= 1
    
    for i in range(1, N):
        diff[i] += diff[i - 1]
    
    print(' '.join(map(str, diff[:N])))

main()

---

この解説は claude4.6opus-thinking によって生成されました。