概要

区間 \([L_i, R_i]\) に一律で \(+1\) を加える操作を \(M\) 回行ったあと、各位置の最終値を高速に求める問題です。

考察

素朴に考えると、各操作ごとに区間内の要素すべてを更新します。つまり操作 \(i\) で \(R_i-L_i+1\) 回加算するため、最悪では - \(N=2\times 10^5\), \(M=2\times 10^5\) - 各操作がほぼ全区間（長さ \(N\)） となり、更新回数は \(O(NM)\) で約 \(4\times 10^{10}\) 回に達して間に合いません（TLE）。

ここで重要な気づきは、「区間全体に同じ値を足す」操作は、各要素を直接更新しなくても、区間の端だけ記録して最後にまとめて復元できるということです。

具体例として、\(N=5\) で操作が \([2,4]\) のとき、最終的には - 2〜4 の範囲だけ +1 になってほしいので、 - 位置 2 から +1 が「始まる」 - 位置 5（=4+1）から +1 が「終わる」 と考えて端点に印を付け、最後に左から累積していけば各要素の値が求まります。

アルゴリズム

差分配列（いもす法 / prefix sum）を用います。

1. 長さ \(N+2\) 程度の配列 diff を用意し、最初はすべて 0。
2. 各操作 \((L, R)\) に対して次を行う：
   • diff[L] += 1（\(L\) から加算が開始）
   • diff[R+1] -= 1（\(R+1\) から加算が終了）
3. 最後に \(i=1..N\) について累積和 cur += diff[i] を取り、cur がそのまま位置 \(i\) の最終値になる。

これは「区間加算」を「端点への更新 2 回」に変換し、最後に累積和で復元しているイメージです。

計算量

• 時間計算量: \(O(N+M)\)（各操作は \(O(1)\)、最後の復元が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列と出力用配列）

実装のポイント

• diff[R+1] にアクセスするため、配列は N+2 以上（コードでは安全に N+3）確保します。

• 入力が最大 \(4\times 10^5\) 個程度の整数になるので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 出力も join でまとめて行うと Python でも十分間に合います。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    diff = [0] * (N + 3)

    idx = 2
    for _ in range(M):
        L = data[idx]
        R = data[idx + 1]
        idx += 2
        diff[L] += 1
        diff[R + 1] -= 1

    cur = 0
    ans = []
    for i in range(1, N + 1):
        cur += diff[i]
        ans.append(str(cur))

    sys.stdout.write(" ".join(ans))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。