概要

区間の共通部分を逐次求めていく問題です。各制限が追加されるたびに、利用可能な区間の左端と右端を更新し、その範囲に含まれる整数の個数を答えます。

考察

素朴なアプローチとして、利用可能な時刻を配列や集合（Set）などで直接管理しようとすると、時刻の最大値が \(10^9\) と非常に大きいため、メモリ制限（MLE）や時間制限（TLE）に引っかかってしまいます。

ここで、「区間と区間の共通部分もまた1つの区間になる」という性質に注目します。 現在の利用可能な区間が \([L, R]\) であり、新たな制限が \([l_i, r_i]\) であるとき、両方の条件を満たす区間は \([\max(L, l_i), \min(R, r_i)]\) となります。

具体例で考えてみましょう。 現在の区間が \([2, 8]\) で、新たな制限が \([5, 10]\) の場合、共通部分は \([\max(2, 5), \min(8, 10)] = [5, 8]\) となります。

このように、現在の左端 \(L\) と右端 \(R\) を変数として保持し、入力を受け取るたびに更新していけば、効率的に答えを求めることができます。 なお、制限が厳しくなり更新後に \(L > R\) となってしまった場合は、共通部分が存在しない（空集合）ため、利用可能な時刻の個数は \(0\) となります。

アルゴリズム

1. 現在の利用可能な区間を表す変数 \(L\) と \(R\) を、初期値で設定します。
2. \(N\) 個の利用制限について、順番に以下の処理を行います。
   • 新たな制限の左端 \(l_i\) と右端 \(r_i\) を読み込みます。
   • 左端 \(L\) を \(\max(L, l_i)\) に更新します（コード内では if l > L: L = l と同義）。
   • 右端 \(R\) を \(\min(R, r_i)\) に更新します（コード内では if r < R: R = r と同義）。
   • 利用可能な時刻の個数 \(count = R - L + 1\) を計算します。
   • もし \(count < 0\) であれば、共通部分が存在しないため \(count = 0\) とします。
   • \(count\) を答えとして記録します。
3. 記録した答えを出力します。

計算量

• 時間計算量: \(O(N)\) 各制限に対する更新処理（\(\max\) や \(\min\) の計算）は \(O(1)\) で行えます。これを \(N\) 回繰り返すため、全体の時間計算量は \(O(N)\) となります。
• 空間計算量: \(O(N)\) 入力を一括で読み込むためのリストや、出力結果を保存するリストを使用するため、\(O(N)\) のメモリを使用します。

実装のポイント

• 入出力の高速化: Pythonでは、標準の input() や print() を何万回も繰り返すと実行時間制限（TLE）になることがあります。そのため、sys.stdin.read().split() で入力を一括で読み込み、出力もリストに貯めてから '\n'.join() で一気に出力する工夫をしています。

• 空集合の判定: \(L\) と \(R\) が逆転して \(R - L + 1\) が負の値になった際、そのまま出力しないように注意が必要です。コード内では if count < 0: count = 0 として適切に処理しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    L = int(input_data[0])
    R = int(input_data[1])
    N = int(input_data[2])
    
    ans = []
    idx = 3
    for _ in range(N):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        idx += 2
        
        if l > L:
            L = l
        if r < R:
            R = r
            
        count = R - L + 1
        if count < 0:
            count = 0
        ans.append(str(count))
        
    sys.stdout.write('\n'.join(ans) + '\n')

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。