UOJ Logo return20071007的博客

博客

一种野蛮处理静态树上在线链查询的做法

2022-01-01 18:57:59 By return20071007

算是个笔记吧。

一棵 $n$ 个点的树,带边权,每次给定 $u,v$ 求从 $u$ 到 $v$ 的路径上的边权乘积,带模数,强制在线。

然后把询问搞得多一点,这个时候就要求我们的查询得要在常数时间内完成。

这里给出一种预处理 $O(n\log n)$(空间同)单次查询 $O(1)$ 的常数巨大的做法。

首先把询问拆成两个点分别到 LCA,这一步显然可以用欧拉序+ST表等方式在这个时空限制内完成。

把树剖一下。然后发现一个点到祖先的路径可以拆成一条“一个点到一个链顶”的路径,和最后一小段一个点到祖先的路径,分别做即可。

对于最后那段查询,它的两个端点在一条重链上,所以在 dfn 序上连续,问题转化为在序列上询问,猫树做掉。

然后之前那些“一个点到一个链顶”的询问,观察到一个点到根至多有 $O(\log n)$ 个链顶,那么可以把所有这样的路径预处理出来然后做掉。

至于如何预处理,可以每个点后面拖个列表表示这个点到根路径上的链顶们的答案。每个点直接从父亲继承这个列表然后每个更新一下,如果自己是链顶那么在列表后面加个数挂着就好了。时空复杂度 $O(n\log n)$。

那么还剩两个事:

  • 给定一个点和一个链顶,找到这个点的列表中这个链顶的出现位置。

对于每种这样的一个点和一个链顶,把答案存下来就好了。因为列表里有这个链顶的点一定都在这个链顶的子树内,dfn 序连续,所以很好算,每个链顶后面拖个位置列表就好了。

  • 之前提到的一个点到祖先的询问中,那个“分界”链顶(也就是前面用上述预处理,后面用猫树)是哪个。

找到祖先点所在链的链顶,按照上述找出现位置的方法找到在那个点的列表中出现在了哪里,进行一个 1 的偏差即可得到分界链顶的位置,进而将其求出(不过其实就不用求出来了,直接查前缀和就好了)。

于是我们的问题就解决了。

板子题还没找到,代码没写过,目测常数巨大。不过如果 $n$ 稍微小一点,似乎是可以接受的(因为常数主要在预处理)。

以上。

评论

暂无评论

发表评论

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