概要

初期区間 \([L, R]\) に対して、制限区間 \([l_i, r_i]\) を順に共通部分として適用していき、各時点で残る整数時刻の個数（区間の長さ）を求める問題です。

考察

共通部分を取る操作を何回繰り返しても、結果は常に「ある1つの区間」になります。
なぜなら、区間同士の共通部分は（空でなければ）また区間になるからです。

\(k\) 個目までの制限を適用した結果の区間を \([curL, curR]\) とすると、 次の制限 \([l, r]\) を適用した後は

• 左端はより右に寄るので \(curL \leftarrow \max(curL, l)\)
• 右端はより左に寄るので \(curR \leftarrow \min(curR, r)\)

と更新するだけで済みます。

素朴に「利用可能な時刻（整数）を全部持って削っていく」などをすると、\(R-L\) が最大 \(10^9\) なので到底扱えず、時間・メモリともに破綻します。
区間を端点（2つの整数）だけで管理すれば、各クエリを \(O(1)\) で処理できます。

また、共通部分が空になる条件は \(curL > curR\) で、そのとき個数は \(0\) です。
空でないとき、整数の個数は端点を含むので \(curR - curL + 1\) になります。

例： - 初期 \([L,R]=[2,10]\) - 制限1 \([4,8]\) → \([4,8]\) 個数 \(8-4+1=5\) - 制限2 \([7,12]\) → \(\max(4,7)=7,\ \min(8,12)=8\) なので \([7,8]\) 個数 \(2\) - 制限3 \([9,9]\) → \([9,8]\) となり空集合、個数 \(0\)

アルゴリズム

1. 現在の共通区間を \(curL=L,\ curR=R\) として初期化する。
2. 各制限 \([l_i, r_i]\) について順に：
   • \(curL \leftarrow \max(curL, l_i)\)
   • \(curR \leftarrow \min(curR, r_i)\)
   • もし \(curL \le curR\) なら \(curR-curL+1\) を出力、そうでなければ \(0\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各制限を定数時間で処理）
• 空間計算量: \(O(1)\)（出力を除く）

実装のポイント

• 個数は「端点を含む」ため \(curR-curL+1\) になる点に注意する。

• \(curL > curR\) になったら空集合なので \(0\) を出す（その後も更新は続けてよい）。

• 入力が大きいので、Python では sys.stdin.buffer.read() のような高速入力を使うと安全です。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    L = int(next(it))
    R = int(next(it))
    N = int(next(it))

    out = []
    curL, curR = L, R
    for _ in range(N):
        l = int(next(it))
        r = int(next(it))
        if l > curL:
            curL = l
        if r < curR:
            curR = r
        if curL <= curR:
            out.append(str(curR - curL + 1))
        else:
            out.append("0")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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