D. GCD and MST 思维 + 数论

题目大意：

有n个点排成一行。每个点有一个值。对于第i到j个点，如果i到j这一部分所有点的值的gcd等于所有点的值的min，那么这两点之间有一条边，长度就为所有点的值的min。此外，如果j=i+1，这两个点之间还会有一条长度为k的边。请你找出这n个点的最小生成树。

题解：

• 首先可以知道， \(gcd(a_i,a_{i+1},...,a_j)=min(a_i,a_{i+1},...,a_j)\) 假设最小值是 \(a_x\) ，那么其实就是找到一个区间 \([l,r]\) \(x\) 属于这个区间，并且 \(a_x\) 整除这个区间任意一个数。
• 所以假设此时最小值是 \(a_x\) ，那么我从 \(x\) 往右，从 \(x\) 往左找到一个整除的区间 \([l,r]\) ，然后继续找下一个最小值 \(a_y\) ，如果 \(y\) 属于区间 \([l,r]\) ，那么就不需要找了，如果不在，那么找他的整除区间，与前面的区间不重叠。
• 然后可以用一个线性的写法 \(ans[i]\) 表示 \(i\) 这个位置的贡献，假设 \(n\) 为根节点。
• 对于每一个点 \(i\) 往后枚举整除的区间，如果整除的 \(ans[j]<=a[i]\) ，那么就停止往前找。
  • 这个是因为如果 \(ans[j]<=a[i]\) ，那么说明 \(ans[j]\) 是被一个小于 \(a[i]\) 的值更新了，并且这个值的位置在 \(i\) 前面，那么可以说明 \(ans[j]\) 也整除 \(a[i]\) ，所以后面的值如果可以被 \(a[i]\) 更新，那么一定也可以被 \(ans[j]\) 更新。
• 总的来说，其实就是找到一个点去更新左右两边的点，然后加上一些优化。
• 但是这个过程中要注意，如果 \(x,y\) 是一个连通块的，那么 \(a[x]\) 更新了 \(ans[y]\) ，那么 \(ans[x]\) 就不能由 \(a[y]\) 更新。
• 最后求总和之后，找到一个 \(ans[x]\) 最大的值减去就是答案。
• 复杂度分析：
  • 如果你理解了这个做法应该可以很容易发现这个是一个 \(O(n)\) 的
  • 因为对于每一个数 \(x\) ，只会往后更新到不是他的倍数了
  • 那么会不会 \(x\) 后面有一个数会重复更新这个区间呢？
  • 加上后面有一个数 \(y\) ，也是在 \(x\) 更新的这个区间之内，那么 \(a[y]>=a[x]\)
  • 往后更新，如果 \(ans[y+1]=a[x]\) ，那么 \(y\) 是会立即停止的，因为 \(ans[y+1]<=a[y]\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn],ans[maxn];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,p;
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),ans[i] = p;
        for(int i=1;i<=n;i++){
            for(int j=i;j<n;j++){
                if(a[j+1]%a[i]!=0||ans[j]<=a[i]) break;
                ans[j] = a[i];
            }
        }
        for(int i=n;i>=1;i--){
            for(int j=i-1;j>=1;j--){
                if(a[j]%a[i]!=0||ans[j]<=a[i]) break;
                ans[j] = a[i];
            }
        }
        ll res = 0;
        int maxs = 0;
        for(int i=1;i<=n;i++) res += ans[i],maxs = max(maxs,ans[i]);
        printf("%lld\n",res - maxs);
    }
    return 0;
}