这一类题带有鲜明的套路:分块,然后将跳大块和跳小块分开计算复杂度,跳大块最多跳 $B$ 次,小块最多暴力更新 $\frac{n}{B}$ 次。

同样考虑维护 $b_i$ 表示 $i$ 第一次跳出所在块会跳到哪里去,那么查询的话就可以两个点往前跳,跳到同一个大块后再继续不断跳 $b_i$ 直到相等,撤回来跳 $a_i$ 即可,单次是 $B+\frac{n}{B}$ 的。

问题在于怎么求 $b_i$,注意到所有点都跳出去后就可以打标记了,如果一个块内还有祖先每跳出块的就暴力重构,一个块被重构的次数是 $O(\frac{n^2}{B^2})$ 的。

取 $B=\sqrt{n}$,时间复杂度为 $O(n\sqrt{n})$ 。

代码:Submission #128873501 – Codeforces

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code