ある配列Aに対して、次のような操作を効率的に行いたいときに使える

1. ある範囲 [l, r) に対して値 x を一括で加算する。
2. 全体をスキャンして、範囲ごとの値を取得する。

以下の例を考える

長さ 10 の配列 A があるとする。初期値はは全て 0 。以下のような操作を考える。

• 区間 [2, 5) に 3 を足したい。
• 区間 [7, 9) に 5 を足したい。

これを差分配列法で解くために、まずはその名の通り差分配列を用意する。

D = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

まずは差分配列に愚直に操作を行う。

• [2, 5) に 3 を足す ⟹ D[2] += 3、D[5] -= 3
• [7, 9) に 5 を足す ⟹ D[7] += 5、D[9] -= 5

D = [0, 0, 3, 0, 0, -3, 0, 5, 0, -5, 0]

そして、配列Dから累積和を取ることで本来の配列Aを求めることができる。

A = [0, 0, 3, 3, 3, 0, 0, 5, 5, 0]

では例題で確認する。

例題 ABC256 D

D - Union of Interval

半開区間の和集合を求める問題。先の考え方を応用して解く。

この問題では左を+1、右を-1とすることで、ある区間の値が全て1となる。これは重複した区間が存在するのなら、その値は1以上となることを意味する。これをうまく使って、開始区間と終了区間をマークしながら答えを出力すればよい。

自分は以下のように実装した。

N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)]

range_diff = [0] * (10**6 + 10)

for l, r in LR:
    range_diff[l] += 1
    range_diff[r] -= 1

inside = 0
fr = -1

for i in range(len(range_diff)):
    if inside == 0 and range_diff[i] > 0:
        fr = i  # 範囲の開始を記録
    inside += range_diff[i]
    if inside == 0 and fr != -1:
        print(fr, i)  # 範囲の終了を記録して出力
        fr = -1