题解：P14109 [ZJCPC 2017] Card Game

· · 题解

不难题。

默认 n,q 同阶。

先把询问离线下来。设 f(x)=\min (r_i\times x+b_i)，发现 f 是凸的，所以可以二分求最大值，现在问题是快速求 f 值。

我们将式子变型：x\times r_i-f(x)=-b_i，其意义是斜率为 x 的直线切点 (r_i,-b_i) 的 最大 横截距，可以把点 (r_i,-b_i) 的凸包维护出来后二分。

所以我们可以直接对询问分块，设快长为 B，每 B 次询问重构，将这 B 次询问涉及的点标记为特殊点，维护非特殊点的凸包，时间复杂度 O(\frac{n^2}{B})；对于询问，先二分，对于非特殊点在凸包上找到二分出最小值，对于特殊点暴力，时间复杂度 O(nB\log n+n\log^2n)。

取 B=\sqrt\frac{n}{\log n}，总时间复杂度为 O(n\sqrt{n\log n}+n\log^2n)，可以通过。

其实数据很水，把凸包跑出来后暴力即可（