Language: C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
const ll INF = 1e15;

class Unionfind{
public:
    vector<int> par,rank;

    Unionfind(int n){
        par.resize(n);
        rank.resize(n);
        rep(i,n){
            par[i] = i;
            rank[i] = 0;
        }
    }

    int find(int x){
        if(par[x]==x) return x;
        else return par[x] = find(par[x]);
    }

    void unite(int x,int y){
        x = find(x);
        y = find(y);
        if(x == y) return;

        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){
        return find(x) == find(y);
    }
};

struct RMQ{

    vector<ll> node;
    int n=1;

    void init(int x){
        while(n < x){
            n *= 2;
        }
        node.resize(4*n,0);
    }

    void update(int s,ll x){
        int i = s + n - 1;
        node[i] = x;
        while(i > 0){
            i = (i-1)/2;
            node[i] = min(node[2*i+1],node[2*i+2]);
        }
    }

    ll getMin(int a, int b){
        return getMin(a,b,0,0,n-1);
    }

    ll getMin(int a,int b,int k, int l, int r){
        if(r < a || b < l) return LONG_MAX;
        if(a <= l && r <= b){ 
            return node[k];
        }
        else{
            ll vl = getMin(a,b,2*k+1,l,(l+r)/2);
            ll vr = getMin(a,b,2*k+2,(l+r)/2+1,r);
            return min(vl,vr);
        }
    }

    int getMinPos2(int a,int b){    
        if(a==b) return a;
        int k = 0;
        ll tmp = getMin(a,b);
        int l = a,r=b;
        while(k < n -1){
            if(getMin((l+r)/2+1,r) == tmp){
                l = (l+r)/2+1;
                k = 2*k+2;
            }
            else if(getMin(l,(l+r)/2) == tmp){
                r = (l+r)/2;
                k = 2*k+1;
            }
            
        }
        return l;
    }

    int getMinPos(int a,int b){
        ll tmp = getMin(a,b);
        int l=a,r=b;
        int k=0;
        while(n > k){
            if(tmp == getMin(l,(l+r)/2)){
                r = (l+r)/2;
                k=2*k+1;
            }
            else{
                l =(l+r)/2+1;
                k=2*k+2;
            } 
        }
        return k-n+1;
    }
};


struct edge { int u,v; ll cost;};
bool comp(const edge& e1, const edge& e2){
    return e1.cost < e2.cost;
}
vector<edge> es;
int V,E;

int main(){
    int n,d,a;
    cin >>n >> d;
    RMQ seg,seg2;
    seg.init(n);
    seg2.init(n);
    Unionfind uf(n);
    vector<ll> A(n);

    rep(i,n){
        cin >> A[i];
        seg.update(i,A[i]+i*d);
        seg2.update(i,A[i]+(n-i-1)*d);
    }


    es.push_back({0,seg.getMinPos2(1,n-1),seg.getMin(1,n-1)+A[0]});
    reps(i,1,n){
        es.push_back({i,seg2.getMinPos2(0,i-1) ,seg2.getMin(0,i-1)+A[i]-(n-i-1)*d});
        if(i<n-1){
            es.push_back({i,seg.getMinPos2(i+1,n-1) ,seg.getMin(i+1,n-1)+A[i]-i*d});
        }
    }


    sort(es.begin(),es.end(),comp);
    ll res = 0;

    rep(i,es.size()){
        edge e = es[i];
        if(!uf.same(e.u,e.v)){
            uf.unite(e.u,e.v);
            res += e.cost;
        }
    }
    cout << res << endl;

}

Compiler output:
a.cc: In member function 'll RMQ::getMin(int, int, int, int, int)':
a.cc:76:35: error: 'LONG_MAX' was not declared in this scope
   76 |         if(r < a || b < l) return LONG_MAX;
      |                                   ^~~~~~~~
a.cc:7:1: note: 'LONG_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
    6 | #include <map>
  +++ |+#include <climits>
    7 |