概要

初期の利用可能時間帯と、複数の利用制限が与えられるので、制限が追加されるごとに利用可能な時間帯の長さを求める問題。

考察

この問題では、初期区間 \([L, R]\) に対して、\(N\) 個の区間制限 \([l_i, r_i]\) を順番に適用していきます。
各区間制限は、現在の利用可能時間とその区間の共通部分（積集合）を取ることに対応します。

つまり、現在の利用可能区間を \([current\_L, current\_R]\) としたとき、新しい制限 \([l_i, r_i]\) が来たときに有効な区間は： $\( [current\_L, current\_R] \cap [l_i, r_i] = [\max(current\_L, l_i), \min(current\_R, r_i)] \)$ となります。

もし \(\max(current\_L, l_i) > \min(current\_R, r_i)\) となった場合は、共通部分が存在せず、空集合となるため、利用可能な時間は0になります。

素朴な方法として、毎回すべての制限を考慮して区間の共通部分を計算する方法が考えられますが、これは毎回 \(O(N)\) かかり、全体で \(O(N^2)\) となって間に合いません（\(N\) が最大 \(10^5\)）。
しかし、実は「すでに適用された制限は今後も常に考慮される」ので、逐次的に現在の有効区間を更新していけば十分です。

アルゴリズム

1. 最初に利用可能な区間 \([L, R]\) を保持する。
2. 各制限 \([l_i, r_i]\) に対して以下の処理を行う：
   • 現在の区間 \([current\_L, current\_R]\) と \([l_i, r_i]\) の共通部分を計算： $\( new\_L = \max(current\_L, l_i), \quad new\_R = \min(current\_R, r_i) \)$
   • もし \(new\_L > new\_R\) なら、共通部分は空集合なので、結果は 0。
   • そうでなければ、区間の長さ \(new\_R - new\_L + 1\) が答え。
   • 新しい区間を次のステップのために保存する。

このようにして、各制限に対して定数時間で処理でき、全体で \(O(N)\) で解けます。

例

初期区間：\([10, 30]\)
制限： 1. \([15, 25]\) → 共通部分：\([15, 25]\) → 長さ：11 2. \([20, 40]\) → 共通部分：\([20, 25]\) → 長さ：6 3. \([5, 18]\) → 共通部分：\([20, 18]\) → 空集合 → 長さ：0

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力を除く）

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。

• 空集合になったら、以降ずっと0になるので、状態を明示的に [0, -1] などにしておくと安全。

• 区間の共通部分の計算は max と min を使うだけで簡単に実現できる。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    L = int(data[0])
    R = int(data[1])
    N = int(data[2])
    
    current_L = L
    current_R = R
    results = []
    
    index = 3
    for _ in range(N):
        l = int(data[index])
        r = int(data[index + 1])
        index += 2
        
        # 区間の共通部分を計算
        current_L = max(current_L, l)
        current_R = min(current_R, r)
        
        # 空集合かどうかを判定
        if current_L > current_R:
            current_L = 0
            current_R = -1
            results.append(0)
        else:
            results.append(current_R - current_L + 1)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。