UOJ Logo zengminghao的博客

博客

二维数点的奇妙乱搞(详细揭秘)

2020-06-17 21:25:10 By zengminghao

【清华集训2015】小Q与找茬

给定二维平面中的 $n$ 个点。有 $m$ 个询问,每次询问给定一个矩形区域,要求回答在矩形中的点的编号。目标是在 1 秒回答正确的次数尽量多。

【题目链接】

算法 1:

将点按照 $x$ 坐标从小到大排序。

对于每次询问,按照 $x$ 坐标二分出点可能出现的区间,并枚举区间中 $y$ 坐标在范围中的点。

提交记录(41pts)

算法 2:

受到算法 1 的启发,我们可以将点分成若干块,并在每块中分别执行算法 1。

将点按照 $x$ 坐标分成 $\dfrac{10^9}{K}$ 个大小为 $K$ 的块。在每块中,将点按照 $y$ 坐标从小到大排序。

计算点可能出现的块。对于每一块,按照 $y$ 坐标二分出点可能出现的区间,并在枚举区间中所有的点。

注意到回答错误是不扣分的,可以不特判边界的两块。

经过实测,取 $K \approx 10^6$ 时算法运行速度较快。

设 $B$ 为块的数量。在数据随机时,程序的时间复杂度约为 $O(m (B + \log \dfrac{n}{B}) + ans)$,但常数非常优秀。

在提交时,这份答案是最快和最短的解。

结论:本题中分块比一大堆 log/polylog 的数据结构跑得快很多。n 方过百万,暴力碾标算!(逃)

评论

lyx_cjz
这题单纯看时间其实不太靠谱,因为时间基本是1s+预处理时间,应该根据返回的正确点数量来判断哪个代码更优秀

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。