D. GCD and MST

思路:

• 首先确定 在最开始的时候 如果只考虑条件2的情况下 实质上n个点已经构成了 一颗权值为 $(n-1)*p$的生成树
• 因此需要做的事情就是 如何在原树的基础上 利用条件1 来更新 某些边 使得生成树的权值变小
• 那么根据Kruskal的思路来看 将每一个点 都放入一个 小根堆中按 点权升序排序 保证每一次更新边权时一定是最小的
• 先确定 当前能选的最小点权 并向两端延伸 使得[L,R]区间内的所有点都满足 是min的倍数 这样就能使得 原来从i<->i+1
• 的这条边 都被更新成 从(L,R-1)//除去min 的点连向下一个点的边 都改成指向min的边 最后再由min指向R 使得 在不破坏原树的树形结构的情况 下 将所有能更新到的边 都给更新了 最终使得最小生成树的边权最小

代码

时间复杂度$O(log(n)+n)$

/*
当你觉得自己不行的时候 你就走到斑马线上 这样你就会成为一个行人
没关系 大不了我们大器晚成而已
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool vis[N];
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        freopen("test.in","r",stdin);
        int t;cin>>t;
        while(t--)
       {
         int n,p;
         cin>>n>>p;
         memset(vis,0,sizeof vis);//记得每次开始初始化一下标记数组 
         vector<int>a(n+1);
         priority_queue<PII,vector<PII>,greater<PII>>q;
         for(int i=1;i<=n;i++)cin>>a[i],q.push({a[i],i});
         LL ans=1LL*(n-1)*p;
         while(!q.empty())
         {
                 auto t=q.top();q.pop();
                 if(t.first>p)continue;
                 int r=t.second;
                 while(r+1<=n&&a[r+1]%t.first==0&&!vis[r])vis[r]=1,r++;
                 int l=t.second;
                 while(l-1>=1&&a[l-1]%t.first==0&&!vis[l-1])l--,vis[l]=1;
                 ans=ans-(1LL*(r-l)*p-1LL*(r-l)*t.first);
         }
         cout<<ans<<endl;
       }
        return 0;
}