本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-02 21:46:52

似乎没有题解提到枚举二进制位这个 trick，就发一篇题解。

由于边的信息可以通过点的信息表示出来，并且边很多，无法直接存储，考虑使用 Boruvka 算法。

考虑每一轮加边该如何处理。

考虑将加边前的图中每个节点所在的连通块编号视为这个点的类别。

考虑正常算法流程，对于每个连通块，都需要找到其他连通块中最优的点，使得本连通块与之建的边权是最小的。

显然，本轮需要加入的边所连接的两个点的类别肯定是不同的。

考虑朴素做法，正着扫一遍再反着扫一遍，扫描的过程中必然需要记录每个类别的最优点是哪个。

这样的话，有 $O(\log V)$ 级别的加边轮数，每次扫描复杂度 $O(n^2)$，炸了。

考虑简化上述过程。上述过程的本质在于任意两个不同类别的点都需要 chk 一次。

考虑这样一个 trick：枚举每个二进制位，仅对类别编号在这一位不同的点对进行处理。

这样的话，每次处理过程只需要 $O(n)$ 扫一遍（不是 $O(n^2)$ 是因为这里从 $n$ 种类别变成了两种类别，即这一位是 $0$ 还是 $1$）。

复杂度变为 $O(n \log n \log V )$ 。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define REP(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
template <class T>
void ckmx(T &a, T b) { a = max(a, b); }
template <class T>
void ckmn(T &a, T b) { a = min(a, b); }
template <class T>
T gcd(T a, T b) { return !b ? a : gcd(b, a % b); }
template <class T>
T lcm(T a, T b) { return a \/ gcd(a, b) * b; }
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template <class T>
void wrint(T x)
{
    if (x < 0)
    {
        x = -x;
        pc('-');
    }
    if (x >= 10)
    {
        wrint(x \/ 10);
    }
    pc(x % 10 ^ 48);
}
template <class T>
void wrintln(T x)
{
    wrint(x);
    pln
}
template <class T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char ch = gc;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = gc;
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = gc;
    }
    x *= f;
}
const int maxn = 2e5 + 5;
int n;
ll d, a[maxn];
struct MS
{
    int fa[maxn];
    int get(int x) { return (fa[x] == x ? x : fa[x] = get(fa[x])); }
    void ms(int a, int b)
    {
        if (get(a) != get(b))
        {
            fa[get(a)] = get(b);
        }
    }
    void init() { FOR(i, 1, n)
                  fa[i] = i; }
} ms;
ll mn[maxn];
int mnid[maxn];
bool at(int s, int i) { return (s & (1 << i)); }
void solve(int id_of_test)
{
    read(n);
    read(d);
    FOR(i, 1, n) { read(a[i]); }
    ms.init();
    ll ans = 0;
    while (1)
    {
        memset(mn, 0x7f, sizeof mn);
        memset(mnid, 0, sizeof mnid);
        bool flg = 0;
        FOR(bit, 0, 17)
        {
            {
                ll _mn = mn[0];
                int _mnid = 0;
                FOR(i, 1, n)
                {
                    _mn += d;
                    if (at(ms.get(i), bit))
                    {
                        if (_mn + a[i] < mn[ms.get(i)])
                        {
                            mnid[ms.get(i)] = _mnid;
                            mn[ms.get(i)] = _mn + a[i];
                        }
                    }
                    if (!at(ms.get(i), bit))
                    {
                        if (_mn > a[i])
                        {
                            _mn = a[i];
                            _mnid = i;
                        }
                    }
                }
                _mn = mn[0];
                _mnid = 0;
                REP(i, n, 1)
                {
                    _mn += d;
                    if (at(ms.get(i), bit))
                    {
                        if (_mn + a[i] < mn[ms.get(i)])
                        {
                            mn[ms.get(i)] = _mn + a[i];
                            mnid[ms.get(i)] = _mnid;
                        }
                    }
                    if (!at(ms.get(i), bit))
                    {
                        if (_mn > a[i])
                        {
                            _mn = a[i];
                            _mnid = i;
                        }
                    }
                }
            }
            {
                ll _mn = mn[0];
                int _mnid = 0;
                FOR(i, 1, n)
                {
                    _mn += d;
                    if (!at(ms.get(i), bit))
                    {
                        if (_mn + a[i] < mn[ms.get(i)])
                        {
                            mnid[ms.get(i)] = _mnid;
                            mn[ms.get(i)] = _mn + a[i];
                        }
                    }
                    if (at(ms.get(i), bit))
                    {
                        if (_mn > a[i])
                        {
                            _mn = a[i];
                            _mnid = i;
                        }
                    }
                }
                _mn = mn[0];
                _mnid = 0;
                REP(i, n, 1)
                {
                    _mn += d;
                    if (!at(ms.get(i), bit))
                    {
                        if (_mn + a[i] < mn[ms.get(i)])
                        {
                            mn[ms.get(i)] = _mn + a[i];
                            mnid[ms.get(i)] = _mnid;
                        }
                    }
                    if (at(ms.get(i), bit))
                    {
                        if (_mn > a[i])
                        {
                            _mn = a[i];
                            _mnid = i;
                        }
                    }
                }
            }
        }
        FOR(i, 1, n)
        {
            if (mnid[i])
            {
                if (ms.get(i) == ms.get(mnid[i]))
                    continue;
                ms.ms(i, mnid[i]);
                flg = 1;
                ans += mn[i];
            }
        }
        if (!flg)
        {
            break;
        }
    }
    printf("%lld\n", ans);
}
int main()
{
    int T;
    T = 1;
    FOR(_, 1, T) { solve(_); }
    return 0;
}