Language: C++

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <numeric>

using LL = long long;
const int kN = 200000 + 5;
const LL inf = 1e17;
int n, d;
int a[kN];
int group[kN];

int find(int x) {
  return group[x] == x ? x : group[x] = find(group[x]);
}

int main() {
  scanf("%d%d", &n, &d);
  for (int i = 0; i < n; ++ i) {
    scanf("%d", a + i);
  }
  std::iota(group, group + n, 0);
  LL result = 0;
  while (true) {
    if ([&]() {
      for (int i = 1; i < n; ++ i)
        if (find(i) != find(0))
          return false;
      return true;
    }()) {
      break;
    }
    using Pair = std::pair<LL, int>;
    using Set = std::set<Pair>;
    std::vector<Set> incs(n), decs(n);
    Set inc, dec;
    for (int i = 0; i < n; ++ i) {
      int g = find(i);
      incs[g].emplace(a[i] + i * 1LL * d, i);
    }
    for (int g = 0; g < n; ++ g) if (!incs[g].empty()) {
      inc.emplace(incs[g].begin()->first, g);
    }
    std::vector<Pair> bests(n, std::make_pair(inf, -1));
    for (int i = 0; i < n; ++ i) {
      int g = find(i);

      inc.erase(std::make_pair(incs[g].begin()->first, g));
      incs[g].erase(std::make_pair(a[i] + i * 1LL * d, i));
      if (!incs[g].empty()) {
        inc.emplace(incs[g].begin()->first, g);
      }

      if (!decs[g].empty()) {
        dec.erase(std::make_pair(decs[g].begin()->first, g));
      }
      decs[g].emplace(a[i] + (n - 1 - i) * 1LL * d, i);
      dec.emplace(decs[g].begin()->first, g);

      if (!inc.empty()) {
        auto it = inc.begin();
        if (it->second == g) ++ it;
        if (it != inc.end()) {
          int p = it->second;
          int j = incs[p].begin()->second;
          LL cost = a[i] + a[j] + std::abs(i - j) * 1LL * d;
          bests[g] = std::min(bests[g], std::make_pair(cost, p));
        }
      }
      if (!dec.empty()) {
        auto it = dec.begin();
        if (it->second == g) ++ it;
        if (it != dec.end()) {
          int p = it->second;
          int j = decs[p].begin()->second;
          LL cost = a[i] + a[j] + std::abs(i - j) * 1LL * d;
          bests[g] = std::min(bests[g], std::make_pair(cost, p));
        }
      }
    }
    for (int g = 0; g < n; ++ g) if (bests[g].second != -1) {
      int a = find(g);
      int b = find(bests[g].second);
      if (a != b) {
        result += bests[g].first;
        group[a] = b;
      }
    }
  }
  printf("%lld\n", result);
}

Compiler output:
a.cc: In function 'int main()':
a.cc:37:10: error: 'vector' is not a member of 'std'
   37 |     std::vector<Set> incs(n), decs(n);
      |          ^~~~~~
a.cc:7:1: note: 'std::vector' is defined in header '<vector>'; this is probably fixable by adding '#include <vector>'
    6 | #include <numeric>
  +++ |+#include <vector>
    7 | 
a.cc:37:20: error: expected primary-expression before '>' token
   37 |     std::vector<Set> incs(n), decs(n);
      |                    ^
a.cc:37:22: error: 'incs' was not declared in this scope
   37 |     std::vector<Set> incs(n), decs(n);
      |                      ^~~~
a.cc:37:31: error: 'decs' was not declared in this scope
   37 |     std::vector<Set> incs(n), decs(n);
      |                               ^~~~
a.cc:46:10: error: 'vector' is not a member of 'std'
   46 |     std::vector<Pair> bests(n, std::make_pair(inf, -1));
      |          ^~~~~~
a.cc:46:10: note: 'std::vector' is defined in header '<vector>'; this is probably fixable by adding '#include <vector>'
a.cc:46:21: error: expected primary-expression before '>' token
   46 |     std::vector<Pair> bests(n, std::make_pair(inf, -1));
      |                     ^
a.cc:46:23: error: 'bests' was not declared in this scope
   46 |     std::vector<Pair> bests(n, std::make_pair(inf, -1));
      |                       ^~~~~