椰子 - 洛谷保存站

本题解的复杂度分析中均视求 $\gcd$ 是 $\mathcal O(1)$ 的。

## 题意

给定 $n$ 的排列 $a$。对于每个数字 $i$，求将排列中值为 $i$ 的数修改为 $1$ 后，所有区间的 $\gcd$ 的种类数。$n \le 2 \times 10^5$。

## 做法

令 $p_i$ 表示值 $i$ 在 $a$ 中的出现位置。有 $p_{a_i} = a_{p_i} = i$。

注意到答案一定是 $n$ 或 $n - 1$。

当 $i = 1$ 时的答案（也就是原序列的答案）一定是 $n$。这是因为长度为 $1$ 的区间的 $\gcd$ 就是这个数本身，而我们可以将这些区间取完。

而对于其它的 $i$，如果存在区间 $[l, r]$ 且 $p_i \not \in [l, r]$ 且 $\gcd (a_l \dots a_r) = i$，那么 $i$ 的答案为 $n$。否则为 $n - 1$。原因与上面类似。

枚举区间，暴力求 $\gcd$ 是 $\mathcal O(n^4)$ 的。如果优化求区间 $\gcd$ 的过程可以做到 $\mathcal O(n^3)$。

同时特殊性质 $A$ 也很好做了。由于 $\gcd(i,i+1)=1$，所以除 $i = 1$ 外所有答案都是 $n - 1$。

考虑正解。我们要优化的是判断是否存在区间 $[l, r]$ 满足：

- $p_i \not \in [l, r]$；
- 且 $\gcd (a_l \dots a_r) = i$。

我们构造一个新序列 $b$，其中：

$$
b_j = \left\{ \begin{matrix} 0 &, p_i = j \\ 0 &,i \nmid a_j \\ \frac{a_j}i &, \text{otherwise.}\end{matrix}\right.
$$

那么原问题等价于判断 $b$ 中是否存在区间 $[l, r]$，满足 $\gcd(b_l \dots b_r) = 1$。

其必要条件是 $b_l\dots b_r \ne 0$。你验证一下发现上面两个条件刚好都满足了。

注意到，如果 $[l, r]$ 是合法的（这里合法指 $\gcd (b_l \dots b_r) = 1$）且 $b_{r+1} \ne 0$，那么 $[l, r + 1]$ 也一定是合法的。但其逆命题是假的。因此我们可以求出每个 $b_j \ne 0$ 的极长连续段，判断这个段内所有元素的 $\gcd$ 即可。

这里**极长连续段**指一个区间 $[l, r]$，满足 $b_l \dots b_r \ne 0$ 且 $b_{l-1}=b_{r+1}=0$（如果 $b_{l-1},b_{r+1}$ 存在）。

此时得到了一个 $\mathcal O(n^2)$ 做法。仍然不够优秀。

注意到 $1 \sim n$ 中所有数的倍数个数和是**调和级数** $\mathcal O(n \log n)$，这就意味着对于每个 $i$ 而言，$b$ 中不为 $0$ 的位置是很少的。因此我们可以优化找极长连续段的过程，总复杂度 $\mathcal O(n \log n)$。

快速求一个区间的 $\gcd$ 可以用 ST 表。

[$\mathcal O(n^3),\mathcal O(n^2),\mathcal O(n \log n)$ 的代码实现](https://www.luogu.com.cn/paste/z3k3vosh)。

正在渲染内容...