CF1588F Jumping Through the Array

题意

有一个长度为 的数组 和一个长度为 的排列 ，对于每一个 有一条有向边 . 有 次如下三种操作：

• 1 l r，询问
• 2 v x，将所有从 出发能到达的节点的编号在 上对应的值加上
• 3 x y，交换 和

题解

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

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

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

由于关键点只有 个，色块也只有 个

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

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

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

每块预处理的时间复杂度为 ，所有修改与询问的时间复杂度为 ，因此总时间复杂度为

代码 codeforces submission 144997997