概要

複数の区間の共通部分（積集合）を順に求め、そのたびに利用可能な時刻の個数を出力する問題です。区間の共通部分は、左端の最大値と右端の最小値を管理するだけで効率的に計算できます。

考察

重要な気づき：区間の共通部分は区間になる

2つの閉区間 \([a, b]\) と \([c, d]\) の共通部分は、

\[[\max(a, c),\ \min(b, d)]\]

という区間になります。もし \(\max(a, c) > \min(b, d)\) であれば共通部分は空です。

例えば、\([2, 10]\) と \([5, 8]\) の共通部分は \([\max(2,5),\ \min(10,8)] = [5, 8]\) で、要素数は \(8 - 5 + 1 = 4\) です。

素朴なアプローチとの比較

素朴に考えると、制限が追加されるたびにすべての時刻を列挙して数える方法がありますが、\(R - L\) が最大 \(10^9\) にもなるため、時刻を1つずつ扱うと TLE になります。

しかし、区間の共通部分は常に1つの連続した区間 \([\text{現在の左端},\ \text{現在の右端}]\) で表せるため、左端と右端の2つの値だけを管理すれば十分です。

累積的に更新できる

\(k\) 個の区間の共通部分は：

\[\left[\max(L, l_1, l_2, \ldots, l_k),\ \min(R, r_1, r_2, \ldots, r_k)\right]\]

です。新しい制限 \([l_i, r_i]\) が追加されるたびに、左端を \(\max\) で、右端を \(\min\) で更新するだけで、正しい共通部分が得られます。

アルゴリズム

1. 現在の利用可能区間を \([L, R]\) で初期化する。
2. 各制限 \([l_i, r_i]\) について：
   • 左端を \(L \leftarrow \max(L, l_i)\) に更新
   • 右端を \(R \leftarrow \min(R, r_i)\) に更新
   • 利用可能な時刻の個数は \(\max(0,\ R - L + 1)\) を出力（\(L > R\) なら空なので \(0\)）

具体例：初期区間 \([3, 15]\)、制限が \([5, 12]\), \([1, 8]\) の場合

ステップ	制限	更新後の \(L\)	更新後の \(R\)	個数
初期	—	3	15	—
1	\([5, 12]\)	\(\max(3,5)=5\)	\(\min(15,12)=12\)	\(12-5+1=8\)
2	\([1, 8]\)	\(\max(5,1)=5\)	\(\min(12,8)=8\)	\(8-5+1=4\)

計算量

• 時間計算量: \(O(N)\) — 各制限につき \(O(1)\) の更新と出力
• 空間計算量: \(O(1)\) — 左端 \(L\) と右端 \(R\) の2変数のみ管理

実装のポイント

• \(L > R\) になった場合（共通部分が空になった場合）、以降どんな制限が来ても空のままです。max(0, R - L + 1) とすることで、この場合を自然に \(0\) として処理できます。

• 一度 \(L > R\) になると、\(L\) は増え続け \(R\) は減り続けるだけなので、再び非空になることはありません。特別な場合分けは不要です。

  ソースコード

L, R = map(int, input().split())
N = int(input())
for _ in range(N):
    l, r = map(int, input().split())
    L = max(L, l)
    R = min(R, r)
    print(max(0, R - L + 1))

---

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