Codeforces Round #714 GCD and MST 混合题

题意

给你一个长度为$n$的数组$a$。以及一个$p$。现在用如下方式生成一张图：

对于任意$i,\ j(i<j)$之间有一条边当且仅当$gcd(a_i,a_{i+1},...,a_j)=min(a_i,a_{i+1},...,a_j)$，且这条边的边长为min(a_i,a_{i+1},...,a_j)。
对于任意的$i$，$i$到$i+1$有一条边长为$p$的边。

现在问，这张图的最小生成树的总边长是多少。

显然我们会立刻想到Kruskal算法。试图寻找最小的边。

首先考虑通过GCD生成的边。

我们可以发现对于$i,\ j(i<j)$，$i\leq{k}\leq{j}$且$a_k=min(a_i,a_{i+1},...,a_j)$（也就是k就是那个最小值）的时候，有$a_k$能整除$a_i$到$a_j$之间的所有值。

于是就有，从$k$出发，向左和向右探索的最远点之间的所有点之间都有边长为$a_k$的边。

于是在$a_k<p$的时候，我们就尽可能的使用这样的边就好了。一旦$a_k\geq{p}$，我们就直接使用长度为$p$的那些边。

现在Kruskal的部分已经比较清晰了，剩下的问题就是怎么从$k$出发找到能被$a_k$整除的最远点。

首先如果我们每次都从$k$出发，依次计算GCD的话显然会是$O(n^2)$的。于是我们就想在并查集上做一些定制。

我们观察$O(n^2)$的做法会发现，其根本问题在于：对于已经连进来了的点，这个做法还会再连一次。

于是很自然的想到，每次寻找都从当前并查集的边界出发。这样就能跳过当前所在集合里的所有点。

所以，除了维护并查集的集合信息，我们还维护集合的左右边界。

如果每次都是从集合边界出发，那么就不可避免的要查询$k$到边界之间的GCD。于是我选择套了一个线段树上去，用于查询区间GCD。