[ABC367E] Permute K times 题解

前言

赛时四发罚时直接葬送 perf，写完还以为是个脑子题，过的人肯定不多。

累了，能不能数据加到 $n\leq 10^7$ 把写 $n\log k$ 的都叉掉（虽然我当时降智地使用了《倍增》来求树上 $k$ 级祖先）。

思路

把每个 $i$ 向 $x_i$ 连边，形成一张 $n$ 个点 $n$ 条边的有向图。

由于每个点出度均为 $1$，这张图实际上是内向基环树森林。

观察到进行 $k$ 次操作对 $a_i$ 的影响实际上就是以 $i$ 为起点在图上走 $k$ 次。

那么可以分类讨论两种情况：$k$ 次操作后，第 $i$ 个点在环上 / 不在环上。

首先拓扑排序一遍找出所有在环上的点，dfs 出每个环的大小并对每个环上的节点从 $0$ 开始进行标号。设某个环的大小为 $s$，手玩发现如果已经走到了该环上的第 $i$ 个节点，还需要走 $x$ 步，则最后一定落在环上的第 $(i+x)\mod s$ 个节点。于是直接从环上的每个节点出发再 dfs 一遍，预处理出每个不在环上的节点将会到达的环上节点与需要走的步数即可。

那么对于 $k$ 步后走不到环上的情况呢？这个问题等价于求树上每个点的 $k$ 级祖先。你当然可以用各种树剖科技或使用另一种解法中的倍增来求解这个问题，但本题的 $k$ 是固定的，你只需要在 dfs 时维护一个双端队列（类似单调队列）。具体地，队列里保存了所有与当前节点深度差 $\leq k$ 的节点，当队列大小 $>k$ 时，弹出队头，队头即为当前节点的 $k$ 级祖先，处理完当前子树后再将队列还原。

那么这题就用 $\mathcal{O}(n)$ 的复杂度做完了。

代码

link，64ms。