cf1029c.md

提示 1： 新增一个区间算交比删去一个区间算交更方便。

提示 2： 删去一个区间，等于使用两侧的区间进行计算。两侧区间的交是新增，而去掉区间是删去，根据提示 1，用两侧的交来计算。两侧区间的交怎么算？

欸，看提示喔。

我们考虑区间交的运算，相当于 左端点取两个区间的最大值，右端点取两个区间的最小值 ，如果左端点大于右端点，则交为空。

于是，新增区间的过程中，我们可以进行上述过程更新左右端点，但删去区间我们没有办法撤销操作。

因此，新增区间会比删去区间方便很多。

考虑枚举每一个删去的区间，计算剩余区间的交，这个交的计算只能用不断求交的方式计算。

我们计算的区间有哪些呢？我们发现前缀和后缀，因此，我们可以 计算前缀区间的交和后缀区间的交，将其再取交，即可完成两侧区间的交的合并。为此，我们只需计算前缀和后缀的左端点的最大值，以及前缀和后缀的右端点的最小值。

时间复杂度为 $\mathcal{O}(n)$ .

具体代码如下（只包含中间处理部分）——

def main():
    n = II()

    ls = []
    rs = []
    for _ in range(n):
        l, r = MII()
        ls.append(l)
        rs.append(r)


    pref_ma_l = [-inf] * n
    pref_mi_r = [inf] * n

    for i in range(n - 1):
        pref_ma_l[i+1] = max(pref_ma_l[i], ls[i])
        pref_mi_r[i+1] = min(pref_mi_r[i], rs[i])

    # 从后往前无需使用数组维护，与前面的数组计算结果结合即可。
    suff_ma_l = -inf
    suff_mi_r = inf

    ans = 0

    for i in range(n - 1, -1, -1):
        ans = max(ans, min(suff_mi_r, pref_mi_r[i]) - max(suff_ma_l, pref_ma_l[i]))
        suff_ma_l = max(suff_ma_l, ls[i])
        suff_mi_r = min(suff_mi_r, rs[i])

    print(ans)