题意
给出 \(n\) 个整数 \(a_i\)。有一个 \(n\) 个点的完全图，定义 \(x,y\neq {x<y}\) 的边权为 \(a_y-a_x\)，问这个图的最小生成树。
思路
完全图最小生成树，考虑 Boruvka 最小生成树算法。
具体的说，初始状态为 \(n\) 个单独的点，因此有 \(n\) 个连通块。
每次对每个连通块找到连接到另一个连通块的最小边权，全部找完后进行连接，若要连接的两个原连通块不在同一连通块中则连接。
随后递归进行以上操作，即可求出最小生成树。
由于每次规模缩小一半，所以复杂度是 \(O(n\log n)\) 的，前提是能快速找到连接另一连通块的最小边权。
对于 \(a_i\)，显然在它的左边的最大 \(a_i\) 和在它右边的最小 \(a_i\) 可能成为连接它的最小边权。
于是我们对 \(i\) 维护在 \(i\) 左边的最大 \(a_i\) 和右边的最小 \(a_i\)，且不在同一连通块中。
可以用一个 set 存下每个连通块的最大最小值，若要求的最大最小值为该连通块，则后移一位即可。
代码
💩💩💩💩💩💩💩
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
int T,n,a[300005],f[300005],f2[300005],mx1[300005],mn1[300005],mnm[300005],mni[300005];
set<pair<int,int>> imx,imn;//最大值，连通块
int lmx[300005],lmn[300005];
int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x];
}
int find2(int x){if(f2[x]!=x) f2[x]=find2(f2[x]);return f2[x];
}
int boruvka(){//1 8for(int i=1;i<=n;i++)f[i]=i,f2[i]=i;int cnt=n,res=0;while(cnt!=1){imx.clear();for(int i=1;i<=n;i++)mnm[i]=inf,mni[i]=0,lmx[i]=0,mx1[i]=0,imx.insert({-inf,find(i)});a[0]=-inf;for(int i=1;i<=n;i++){mx1[i]=lmx[prev(imx.end())->second];if(find(mx1[i])==find(i)){if(imx.size()>1)mx1[i]=lmx[prev(prev(imx.end()))->second];elsemx1[i]=0;}imx.erase({a[lmx[find(i)]],find(i)});if(a[i]>a[lmx[find(i)]])lmx[find(i)]=i;imx.insert({a[lmx[find(i)]],find(i)});}imn.clear();for(int i=1;i<=n;i++)lmn[i]=0,mn1[i]=0,imn.insert({inf,find(i)});a[0]=inf;for(int i=n;i>=1;i--){mn1[i]=lmn[imn.begin()->second];if(find(mn1[i])==find(i)){if(imn.size()>1)mn1[i]=lmn[next(imn.begin())->second];elsemn1[i]=inf;}imn.erase({a[lmn[find(i)]],find(i)});if(a[i]<a[lmn[find(i)]])lmn[find(i)]=i;imn.insert({a[lmn[find(i)]],find(i)});}for(int vl,id,i=1;i<=n;i++){if(mx1[i]==0) id=mn1[i];else if(mn1[i]==0) id=mx1[i];else if(a[i]-a[mx1[i]]<=a[mn1[i]]-a[i]) id=mx1[i];else id=mn1[i];vl=(id<i?a[i]-a[id]:a[id]-a[i]);if(vl<mnm[find(i)]){mnm[find(i)]=vl;mni[find(i)]=id;}}for(int i=1;i<=n;i++)f2[i]=f[i];for(int i=1;i<=n;i++){if(mni[find(i)]==0) continue;int xx=find2(i),yy=find2(mni[find(i)]);if(xx!=yy){res+=mnm[find(i)];f2[xx]=yy;cnt--;}mni[find(i)]=0;}for(int i=1;i<=n;i++)f[i]=f2[i];}return res;
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cout<<boruvka()<<endl;}return 0;
}
)
