题解：P11407 [RMI 2020] 寻线 / Nice Lines
伊地知虹夏
·
·
题解
Description
有 n 条隐藏的直线 l_i:y = a_ix + b_i，你可以询问交互库一个实点 p = (x,y)，交互库会返回一个实数 F(p) = \sum\limits_{i=1}^{n} {\rm dis}(p,l_i)，你需要通过 4n+\mathcal O(1) 次询问找到所有直线。
Analyze
考虑 (x,y) 这样的查询给了我们两维的自由度，不太好利用。我们固定 p 在一条直线 \rm k 上移动，考察 {\rm dis}(p,l_i)，我们发现它是一个绝对值函数。那么由于 F(p) 是 n 个绝对值函数的叠加，则 F(p) 是一个分段线性函数。
我们发现 F 的拐点是直线 l_i 和 \rm k 的交点，取 {\rm k}: x = 2\times 10^4 即可解出 l_i。
接下来问题变成求分段线性函数的所有拐点，首先显然有一个 \mathcal O(n \log V) 分治做法。
考虑优化，注意到分治过程中有很多无效递归，比如当区间只有一个拐点时依然在进行递归，但实际上我们可以通过 \mathcal O(1) 次查询找到它。
具体来说，求出区间最左边的直线和最右边的直线，求它们的交点 (x,y)，那么如果 y = F(x)，停止递归，返回交点。
我们分析这样做的询问次数：开始递归要找到左右边界处的直线，代价为 4。判断区间能否递归需要询问交点函数值，代价为 1。每次递归要找出交点函数值所在的直线，代价为 2。由于分治过程形成一颗二叉树，总共递归 n-1 次，代价为 (2 + 1) \times (n - 1) + 1\times n + 4 = 4n + 1。