题解：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)$，可以通过。

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