CF1588F Jumping Through the Array

题意

你有个长度为 \(n\) 的数组 \(a\) 和一个长度为 \(n\) 的排列 \(p\)，对于每一个 \(i\) 有一有向边 \((i,p_i)\)。

有如下三种操作：

• 1 l r 询问 \(\sum_{i=l}^r a_i\)。

• 2 v x 将所有 \(v\) 能到达的节点所对应编号的值加 \(x\)。

• 3 x y 交换 \(p_x\) 与 \(p_y\)。

对于每一 \(1\) 操作输出结果。

题解

先分析一下题目，显然这个序列抽象成图之后会变成一堆环。

首先考虑只有前两个操作的情况下怎么做。

首先这种形状的图一般数据结构不太好维护，考虑分块。
我们要找到一种方法使得每次操作只有 \(O(\sqrt{n})\) 的级别。

先分析一下操作在图上的影响。
操作二是给所在环整体加上一个数。
操作一就是原序列的值之和与环上的影响整合。

首先操作二直接给环上打 \(tag\) 即可。
操作一若直接在序列上搞不太好做，考虑从环上得到对序列的影响。
显然只有被操作过的环有贡献，也就是说环的数量是由操作次数来定的。

注意到我们可以用一次操作来将所有环上的贡献对应到序列上。
所以我们可以用类似一个根号重构的方式来搞这东西。
每 \(\sqrt{n}\) 次操作将环上的贡献对应到序列上，而下一段也只会增加 \(\sqrt{n}\) 个环，中间我们只枚举操作过的环就可以做到每次操作在 \(\sqrt{n}\) 的级别。

这样就解决了没有操作三的情况。

类似的，我们可以发现操作三是将一个环分裂成两个环或者是将两个环并在一起。
若没有分裂的情况，显然可以直接套用之前的方法来解决。
若有分裂的情况就不太好办了。

考虑只有合并为什么是可行的，因为每个环的内部结构是不变的。

所以同样的，我们找到每一个环中不变的地方。
注意每 \(\sqrt{n}\) 段操作三至多影响到 \(2\sqrt{n}\) 个点，将这些点称作黑点，我们提前将这一段操作中的黑点预处理出来。
显然对于一个环中一个黑点往回找，一直找到上一个黑点为止，中间的白点与最开始的黑点即为不变的部分，这就把环切成了一段一段的。
我们将每一段看做一个点，我们直接嗯维护这 \(2\sqrt{n}\) 个点形成的图即可。

最后找到一段中与给定区间重合的数量可以对每一段提前排好序后二分。
这样做每次就是 \(O(\sqrt{n}logn)\)，这时块长取 \(\sqrt{\frac{n}{logn}}\)，可以将时间复杂度平衡至 \(O(n\sqrt{nlogn})\)。
实际上可以通过预处理去掉二分，这样时间复杂度就仍然是 \(O(n\sqrt{n})\)。

实际上这就是操作分块，将多个操作连在一起处理。

我的代码比较奇特，使用了二分，但是块长取 \(\sqrt{n}\) 才能过，而取了 \(\sqrt{\frac{n}{logn}}\) 反而过不去，比较玄学。code

...

实际上没有三操作的就是普通的分块。
但有了三操作这题才是有了灵魂。
我们通过操作分块可以提前得到后面的条件从而进行处理。