UOJ Logo supy的博客

博客

标签
暂无

UOJ341的另一种写法&有关其复杂度的问题

2019-01-25 12:55:56 By supy

这里只讨论末尾加入的操作(末尾删除复杂度相同,头部操作大概不是瓶颈) 标算的写法是枚举每个约数更新约数的约数,对于单次操作$x$,复杂度为$O(\sum_{i|x}d(i))$。

我写的是另一种写法:从后往前更新约数的dp值,维护目前所有dp值改变的位置集合,更新dp值就枚举集合中每个位置,如果是倍数就进行修改。 这样复杂度似乎不好分析,因为一个位置只有dp值改变才会加入集合。这样单次最坏是$O(d(x)^2)$的(这当然很大)。 但是实际运行速度很快,UOJ上目前是rk1,代码http://uoj.ac/submission/318055

我很想知道这个写法的复杂度到底是什么。

共 1 篇博客