核弹来了，提出一种复杂度不一定更优秀但是比较神奇的做法

zhangshirui · 2026-10-19 08:59:26 · 题解

可以做到 n\sqrt{m+k\cdot \log k}，在这题里可能不是很优秀。

首先有一个结论，大小至少为 B 的分治中心的个数为 O(\frac nB)，原因是，点分治上每层的点集只有包含和不交两种关系，而如果如果包含则一个至少是另一个的两倍。因此可以将它们按照大小 [B,2B),[2B,4B),\dots,[2^kB,2^{k+1}B) 分组，根据上面内容，同一组内的分支中心涉及的点是不交的，因此总共的分治中心数量最多为 \sum_{k=0}^{+\infty}{\lfloor \frac{n}{2^kB}\rfloor}，这个显然是 O(\frac nB) 的。

因此在这题中，可以设计出下面算法：当当前分支中心的大小大于 B，则处理出所有深度的点的数量，然后用 NTT 卷一下，之后遍历每个询问 check，这可以做到 O(m+k\log n) 处理一个分治中心，然后若小于等于 B，可以直接暴力 B^2 处理所有点对，然后不用递归，这部分因为点数和是 n，因此总体也最多 nB。根据上面的结论，可以得到复杂度为 O(\frac{n\cdot(k\log k+m)}{B}+nB)，然后 B 取 \sqrt{m+k\cdot \log k} 即可得到开头的复杂度。

实现时注意这里要容斥每个儿子内部的贡献，你也需要特判每个儿子是否大小大于 B，判断使用暴力枚举点对容斥还是用 NTT 卷出来再枚举询问容斥。

如果 k 小点 m 开大点我这个做法显然是比较占优的。

这个思路最开始是我和 GPT5 讨论一个其他题时候 GPT 给出了上面的结论。然后我想了一下，发现多个询问的点分治好像都可以用这个优化，遂写在这里。或许不能保证人类贡献大于 AI 贡献？毕竟感觉都没见到过这个 Trick，AI 提出来性质感觉后面的都很自然。或许该叫它截断点分治？本质上是一个点分治结合根号分治的做法。