半平面莫队

· · 算法·理论

很久之前就会大概做法了。今天思考了一下细节，非常有趣。

可以在 [Ynoi2003] 赫露艾斯塔 了解半平面莫队的定义和基本构造方式。当然这个题并不需要找到变化的点。

方便起见 n=m。

随机取 \sqrt n 个关键点。然后对询问的半平面，找到距离其最近的关键点，将半平面的直线平移到关键点上，这其中有期望 \sqrt n 个点。然后对每个关键点把直线按照斜率排序。

可以发现两个瓶颈：\sqrt n 次的对 n 个点到某个关键点的连线斜率排序和找平行线之间的点。

先考虑前者。我们有一个非常暴力的思路：每次再随机取 \sqrt n 个点，以关键点到这些点的连线划分平面。那么每个区域里面还是期望有 O(\sqrt n) 个点，那么就无需排序了，可以直接把询问按区域归类。我们需要快速地找到每个区域中的点。

对于后者，首先我们知道一种直接每 \sqrt n 个点分一组后旋转扫描线的算法。但这东西需要对斜率排序，会带 \log。

考虑一个类似 KDT 的平面划分结构，但得更强：我们用两条直线划分平面，将点集均分为四部分。这样一个半平面在上面递归，每次只会递归到三个子树。T(n)=3T(n/4)+O(1)，那么有 T(n)\approx O(n^{0.79})。显然把平行线放在上面递归的复杂度也是一样的。前者也一样。

随意地取 B=n^{0.4}。然后当子树大小 \le B 时采用旋转扫描线预处理。那么现在询问的时间复杂度被降低到了 \tilde O(n^{0.474})，而预处理旋转扫描线的复杂度也仅仅是 \tilde O(n^{1.4})，所以总的复杂度是 O(n^{1.5})。

最后一个问题：如何建树？

我们先选择一条平分点集的直线，比如 x 的中位数，将直线左侧的点称为红点，右边的称为蓝点。考虑一个半平面 P，钦定这个半平面中包含了一半的红点。那么如果确定 P 的角度 \theta，那么 P 其实就被确定了。\theta=0 和 \theta=\pi 这两种情况 P 中分别包含了 t 个和 n-t 个蓝点。根据介值定理，必然能找到一个 \theta 使得 P 包含了一半的蓝点。于是直接二分，取包含 n/2 的区间即可。

对于一般情形，只需要取 \sqrt m 个关键点，B\approx m^{0.56} 就能做到大约 O(n\sqrt m+m^{0.56}n^{0.88}) 的复杂度，还是比较遗憾的。因为我们知道二维莫队可以规约到半平面莫队，只要将点排成 L 字形。