YBTOJ&洛谷P3292:幸运数字(线性基、点分治/倍增)

解析
虽然使用三个log的倍增算法艹过去了 但是我们还是来聊聊正解吧
考虑点分治 对于当前的根,dfs求出联通块内每个点到当前根的线性基 一条路径的答案应该在路径出现上第一个成为根的点时统计到 具体来说,就是路径的两端点在同一个solve函数的不同子树内 通过奇怪的时间戳标记可以实现 对于询问,每个结点开个vector暴力遍历即可 由于每个结点最多被dfslog遍,所以复杂度是对的 复杂度瓶颈在dfs求线性基上,时间复杂度

n

l

o

g

2

n

YBTOJ&洛谷P3292:幸运数字(线性基、点分治/倍增)最先出现在Python成神之路

版权声明:
作者:admin
链接:https://www.techfm.club/p/7719.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>