ARC 129
Table of Contents
B - Range Point Distance
$dist(l, r, x) = \max(0, l-x, x-r)$ であるから
\begin{align} \max(dist(L_1, R_1, x)&, \cdots, dist(L_k, R_k, x)) \ &= \max(0, L_1 - x, x - R_1, \cdots, L_k - x, x - R_k) \ &= \max(0, \max(L_1 - x, \cdots, L_k - x), \max(x - R_1, \cdots, x - R_k)) \end{align} である.
\begin{align} &\max(L_1 - x, \cdots, L_k - x) = \max(L_1, \cdots, L_k) - x = A_k - x\ &\max(x - R_1, \cdots, x - R_k) = x + \max(-R_1, \cdots, -R_k) = x - \min(R_1, \cdots, R_k) = x - B_k \end{align} where $A_k = \max(L_1, \cdots, L_k)$ and $B_k = \min(R_1, \cdots, R_k)$.
$A_k \leq B_k$ のときは最大値は 0 とできる.
$A_k > B_k$ のとき $y = A_k - x$ と $y = x - B_k$ の 交点 $\displaystyle \left( \frac{A_k + B_k}{2}, \frac{A_k - B_k}{2} \right)$ の $y$ 座標の値が最大となる.
$A_k + B_k$ が奇数のときは $\displaystyle x = \mathrm{ceil}\left(\frac{A_k + B_k}{2}\right), \mathrm{floor}\left(\frac{A_k + B_k}{2}\right)$ のときに最大値 $\displaystyle \mathrm{ceil}\left(\frac{A_k - B_k}{2}\right)$ となる.