题解 | #聊天# 区间合并，非暴力解法

对于一个A的空闲时间段 [a, b] 和一个B的空闲时间段 [c, d]，我们要找的是：t取何值时，将 [c+t, d+t] 与 [a, b] 有非空交集？

在草稿纸上简单画图模拟一下，可以得到 。

当然，题目中还有一个限制：那就是B的起床时间要在 [l, r]之内。因此将 [d-a, b-c] 再与 [l, r] 取交集，得到最终的区间为

遍历每一对A和B的空闲时间段，得到了 p*q 个区间。此时使用区间合并这一问题的思路，最终得到符合条件的起床时间数量。

时间复杂度：O( pq*log(pq) )

from collections import defaultdict
def solve():
    p, q, l, r = [int(x) for x in input().split()]
    A, B = [], []
    intervals = []
    for _ in range(p):
        A.append([int(x) for x in input().split()])
    for _ in range(q):
        B.append([int(x) for x in input().split()])
    for a, b in A:
        for c, d in B:
            s, e = max(l, a - d), min(r, b - c)
            if l <= s < e <= r:
                intervals.append((s, e))
    intervals.sort()
    ans = 0
    a = b = l
    for s, e in intervals:
        if s <= b:
            b = e
        else:
            ans += b - a + 1
            a, b = s, e
    ans += b - a + 1
    print(ans)

while 1:
    try:
        solve()
    except:
        break