UOJ Logo matthew99的博客

博客

《共价大爷游长沙》解题报告

2016-06-26 19:37:35 By matthew99

题目地址

http://uoj.ac/problem/207

Q&A

题目名称怎么来的?

本题题名是跟风另外两道题目的,另外两道题目的题目名见题面第一句话。

共价大爷和小L是谁?

共价大爷的ID是zhangzj,是目前雅礼机房的红太阳,神通广大,无所不能,切题如麻,所向披靡。

小L的ID是luoyuchu,他是共价大爷的忠实粉丝。

长沙市真的总是在不断的施工吗?

的确是的,比如说从雅礼到我现在住的地方就有多处施工点。雅礼操场目前在施工,已经挖出了多座古墓,甚至曾经被以为是太守坟。

算法一

直接上暴力,每次对于所有路径将它经过的边边权加一,然后看看询问的路径边权是否为$|S|$,时间复杂度$O(n ^ 2m)$,期望得分10分。

算法二

如果没有加边删边操作和删除点对操作,那么我们可以维护当前的可行路径,每次可以用$O(\log n)$或者$O(1)$时间进行树上路径求交以及判断一条边是否在路径上,如果使用倍增,则时间复杂度为$O((n + m)\log n)$,期望得分20分,结合算法一可以获得30分。

算法三

如果没有加边删边操作,那么我们可以用动态树或者树链剖分等支持链修改单点询问的结构,维护每个点被路径经过的次数,每次看看询问边的两个端点是否都被经过了$|S|$次。如果使用LCT那么时间复杂度$为O((n + m) \log n)$,期望得分40分,结合算法一可以获得50分。

算法四

对于没有加边删边操作的数据,我们还有一种做法,我们对所有点对建一棵线段树,每个节点存子树中所有路径的交,每次操作的时候都很容易在线段树上update解决,如果用ett序或者dfs序加ST表,那么每次可以在$O(1)$的时间内update,总时间复杂度为$O(n \log n + m \log m)$,期望得分40分,结合算法一可以获得50分。

算法五

对于$|S| \le 10$的数据,我们可以每次询问的时候进行和算法三类似的操作,每次暴力加入所有路径维护每个点被经过的次数再用同样的方法询问,期望得分20分,结合前面的算法可以获得70分。

算法六

我们注意到,一条$x$到$y$路径被所有路径经过,当前仅当以$x$为根时,所有路径的端点都恰好有一个在$y$的子树中。这样,我们对每一个路径随机一个权值,然后每次加入删除路径时,将两个段点的点权异或上这个权值,然后用动态树维护子树权值异或和,每次询问对应子树内的权值异或和是否是当前所有路径的权值异或和,权值如果设为$10 ^ 9$级别,就基本不可能出错了。时间复杂度$O((n + m) \log n)$,空间复杂度$O(n)$,可以通过全部数据。

算法七

这题罗哲正同学提出了另外一种做法,我们可以将权值异或在一条链上,新加入一条边的时候,新形成的环上必然有一条边会被删除,假设这条边是$u$和$v$之间的边。我们发现,将这条被删除的边的权值异或到删除这条边后$u$和$v$之间的路径上,就可以更新新树上对应的权值了。时空复杂度均和算法六一样,也可以通过全部数据。

评论

yanQval
前排跪毛爷爷
ljss
@
kexinyu
@
kexinyu
@@
Itache
orz

发表评论

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