UOJ Logo zx2003的博客

博客

NOI2019D2T1的 O(n logn) 算法

2019-09-18 20:21:11 By zx2003

感觉也不是很难,不过先前没听人提过。

显然题意可以转化为给定二维平面上的若干个点和若干个矩形,然后需要按某个特定的顺序取出矩形中的所有点。

一个简单的做法是对 $x$ 这一维建线段树,对线段树的每个节点维护一个set,每次需要取出点的时候就在set里通过lower_bound逐个找到需要的点。

这样复杂度是 $O(n\log^2n)$ 。

更优秀的做法是把所有点的 $y$ 坐标和询问矩形的下边界排个序,从小到大进行扫描线,同时维护出每个矩形在线段树的每个节点上lower_bound的结果。

取出点的时候,在线段树的每个节点上我们需要执行的操作是1.找到某个位置往后第一个没被删除的点;2.删除某个点。

显然这可以使用并查集做到线性,链接在这里

代码在这里

为了方便实现以及实践效率,该代码中并没有使用线性并查集。

由于数据太水,运行时间被kdtree吊打。

反正数据结构的技能点不是技能点,打表的技能点才是技能点,随便出个T1数据乱造就好了对吧。

评论

immortalCO
根据出题人的 PPT 和他的口述,数据是随机的,因为越是随机的数据 K-D Tree 跑的越慢,这样反而能把标算卡到尽量慢。 在不了解情况的时候直接进行批判,这样的行为……是不是……不是特别的合适呢?
zx2003
@immortalCO 如果数据随机,那么很多点在一开始就会被访问到,kdtree的很多子树很快就会变空,导致后面的矩形定位中只要加上子树为空就不做的剪枝,运行时间就根本卡不满。 由此,对于“因为越是随机的数据 K-D Tree 跑的越慢,这样反而能把标算卡到尽量慢”,可能是因为标算去掉了一些平凡的剪枝。 说不定标算是先框出kdtree上的根号个子树,然后再逐一取出这些子树里的点。

发表评论

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