UOJ#553. 【UNR #4】己酸集合

> 给定平面上的 $n$ 个点，有 $q$ 次询问，每次询问给出一对 $(z, r)$，试求出与点 $(0, z)$ 的欧几里得距离不超过 $r$ 的点的个数。
>
> $n \le 1.2 \times 10^4, q \le 10^6$。

感谢 @[kernel_panic](https://www.luogu.com.cn/user/329316) 跌教会了我半平面数点这个东西！

注意到题目要求的东西，其实就是满足 $x_i^2 + (y_i - z)^2 \le r^2$ 的 $i$ 的个数。我们把式子拆一下，可以写成：

$$
\begin{aligned}
  x_i^2 + (y_i - z)^2 &\le r^2 \\
  x_i^2 + y_i^2 - 2 y_i z + z^2 &\le r^2 \\
  -2 y_i z + x_i^2 + y_i^2 &\le r^2 - z^2
\end{aligned}
$$

由于 $x_i, y_i$ 是定值，我们可以将左式视作一个过定点 $(0, x_i^2 + y_i^2)$ 的斜率为 $z$ 的一次函数，那么很明显这个东西是一个形如 $kx + b \le y$ 的半平面。因此原问题也就是等价于在斜率 $z$ 固定时包含点 $(-2y_i, r^2 - z^2)$ 的半平面个数。

记 $f_i(t) = zt + x_i^2 + y_i^2$，可以看出斜率 $z$ 与 $f_i(-2y_i)$ 之间也为线性关系。因此我们考虑一个升序序列 $a$，用于在 $z$ 变化时动态维护 $f_i(-2y_i)$ 间的大小关系。那么容易发现对于某一个询问，其答案都一定对应了 $a$ 的一个前缀。

现在问题就来到了如何维护这个 $a$ 上。由于 $f$ 都为一次函数，我们可以发现，当 $z$ 变化时，对于任意一对 $i, j$，$f_i(-2y_i)$ 与 $f_j(-2y_j)$ 之间的大小关系最多可能变化一次。因此，会使得序列 $a$ 发生变化的斜率 $z$ 实际上只有 $\mathcal{O}(n^2)$ 个。

那么现在做法就比较明显了。考虑将询问离线，再按照 $z$ 的大小升序排序，预处理出上述的会使 $a$ 发生变化的 $z$ 的值，然后对 $z$ 进行扫描线。在扫描的过程中，我们暴力的维护 $a$（即每遇到一个变化点就暴力交换其对应的 $i, j$ 的值），再二分处理询问即可。由于变化点有 $\mathcal{O}(n^2)$ 个，这个做法的时间复杂度为 $\mathcal{O}((n^2 + q) \log n)$，还不够好。

我们考虑分块，再对每一块处理所有的询问。记块长为 $B$，则时间复杂度为 $\mathcal{O}\left(\frac{n}{B} (q + B^2) \log B\right)$，取 $B = \sqrt q$ 时最优，能够做到 $\mathcal{O}(n \sqrt q \log q)$。

注意到这个分块对块内的点实际上是没有任何限制的，因此在解决其他类似问题时，可以考虑从点的顺序上下点功夫再分块！