菜王的 blog

这不比 A 火？这不比 A 火？这不比 A 火？这不比 A 火？

考虑每次加入一个 $(A_i, B_i)$ 并动态维护答案。考虑维护 $L(x)$ 表示右端点为 $x$ 时左端点的最大值，那么 $ans = \min\{x - L(x)\}$。显然 $L(x)$ 单调不降。

假设 $A_i \le B_i$，设加入 $(A_i, B_i)$ 后的新的 $L(x)$ 为 $L'(x)$，那么显然有：

$L'(x) = \begin{cases} \min(B_i, L(x)) & B_i \le x\\ \min(A_i, L(x)) & A_i \le x < B_i\\ -\infty & x < A_i\\ \end{cases}$

由于 $L(x)$ 单调不降，所以区间取 $\min$ 相当于区间推平，直接维护即可做到 $O(n \log n)$。

具体地，维护该函数的极长连续段 $(l, r, y)$ 的集合 $S$（即 $x \in [l, r]$ 时 $L(x) = y$），那么 $ans = \min_{(l, r, y) \in S}\{l - y\}$。颜色段均摊分析得出 $S$ 最多变化 $O(n)$ 次，同步维护 $l - y$ 的集合即可。显然这是可以支持强制在线的。