考虑如何去掉这个绝对值，
换句话说，如何减少边数并且能建出 MST。
在求解偏序问题时，往往会分而治之，
这样原来 (O(n^2)) 的做法就能够被优化。
考虑将所有点对半折开，
左半部分和右半部分的建边分治处理，
只考虑横跨两部分的建边，
若左半部分的点为 (j)，右半部分的点为 (i)
边权就可以转换成：
[(A_i+i imes d)+(A_j-j imes d)
]
既然 (i) 和 (j) 独立出来，那么只需要选出
右半部分 (min{A_i+i imes d}) 所对应的 (i)，
左半部分 (min{A_j-j imes d}) 所对应的 (j)，
将 (j) 与右半部分所有点连边，(i) 同理。
那么这样就只有 (O(nlog n)) 条边，
用 Kruskal 跑最小生成树就可以做到 (O(nlog^2n))。
Code
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=200011; typedef long long lll;
struct node{int x,y; lll w;}e[N<<5];
lll a[N],b[N],D,ans; int n,f[N],m;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
bool cmp(node x,node y){return x.w<y.w;}
inline signed getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
inline void dfs(int l,int r){
if (l==r) return;
rr int mid=(l+r)>>1,t0=l,t1=r;
for (rr int i=l;i<=mid;++i)
if (a[t0]>a[i]) t0=i;
for (rr int i=r;i>mid;--i)
if (b[t1]>b[i]) t1=i;
for (rr int i=l;i<=mid;++i)
e[++m]=(node){i,t1,a[i]+b[t1]};
for (rr int i=r;i>mid;--i)
e[++m]=(node){t0,i,a[t0]+b[i]};
dfs(l,mid),dfs(mid+1,r);
}
signed main(){
n=iut(),D=iut();
for (rr int i=1;i<=n;++i){
rr int x=iut(); f[i]=i;
a[i]=x-i*D,b[i]=x+i*D;
}
dfs(1,n),sort(e+1,e+1+m,cmp);
for (rr int i=1;i<=m;++i){
rr int fa=getf(e[i].x),fb=getf(e[i].y);
if (fa!=fb) f[fa]=fb,ans+=e[i].w;
}
return !printf("%lld",ans);
}