CF1588F Jumping Through the Array

题意

有一个长度为 $n$ 的数组 $a$ 和一个长度为 $n$ 的排列 $p$，对于每一个 $i$ 有一条有向边 $(i, p_i)$. 有 $q$ 次如下三种操作：

• 1 l r，询问 $\sum\limits_{l\le i\le r}a_i$
• 2 v x，将所有从 $v$ 出发能到达的节点的编号在 $a$ 上对应的值加上 $x$
• 3 x y，交换 $p_x$ 和 $p_y$

$n,q\le2\times 10^5$

题解

考虑对操作序列分块，每块结束后暴力重构

由于 $p$ 始终是一个排列，在任一时刻所有边构成的图是若干个环

注意到每次操作3会更改两个点的出边，在同一个操作序列的块中的这样的点将图分为若干色块，每个色块在这个操作序列的块中都不会发生改变

示意图

由于关键点只有 $\mathcal{O}(\sqrt{n})$ 个，色块也只有 $\mathcal{O}(\sqrt{n})$ 个

操作2就是在所有能到达的色块上打一个加法标记

考虑操作1
对于每一个询问我们将其差分为两个前缀和，也就是一个块内一共询问 $\mathcal{O}(\sqrt{n})$ 个前缀和
由于一共只有 $\mathcal{O}(\sqrt{n})$ 种颜色和 $\mathcal{O}(\sqrt{n})$ 个有用的前缀和，可以 $\Theta(n)$ 预处理出在所有用到的前缀和中每种颜色的点的个数

重构的时候，每个数加上它所在色块的加法标记

每块预处理的时间复杂度为 $\Theta(n\sqrt{n})$，所有修改与询问的时间复杂度为 $\mathcal{O}(n\sqrt{n})$，因此总时间复杂度为 $\Theta(n\sqrt{n})$

代码 codeforces submission 144997997