CF888G Xor-MST

· · 题解

对于完全图的MST问题，一般考虑使用Boruvka算法，我们要在nlogn或nlog^2n时间内求出每个连通块最小的连接的边，而这个边权一般可通过点权以一定方式求出。

对于本题来说，要求的就只是点权异或最小值，考虑用01trie维护，对全局建一棵trie，然后对于每个连通块建一棵trie，每次Boruvka算法合并两个联通块时，合并相应的trie，在trie上维护子树size，点权异或最小值就直接在全局trie与当前连通块的trie的size作差得到的树上贪心即可。总共会迭代logn次，所以总时间复杂度为\Theta(nlog_nlog_{size})，空间复杂度为\Theta(nlog_{size})

\large Code: 
int a[200001], cnt, ch[200001 * 50][2], siz[200001 * 50], minn[200001], nxt[200001], fa[200001], tail[200001 * 50], tmp[200001], st[200001], top, root[200005];
inl int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
inl void insert(int &x, int dep, int i, int w) {
    if (!x)x = ++cnt;
    if (dep < 0)return (void)(tail[x] = i, siz[x] = 1);
    bool c = w >> dep & 1;
    insert(ch[x][c], dep - 1, i, w), siz[x]++;
}
inl void merge(int &p, int q) {
    if (!p || !q)return (void)(p = p + q);
    merge(ch[p][0], ch[q][0]), merge(ch[p][1], ch[q][1]);
    siz[p] = siz[ch[p][0]] + siz[ch[p][1]], tail[p] = tail[q];
}
inl pair<int, int> query(int x, int pre, int w) {
    int ans = 0;
    for (re i = 30; ~i; i--) {
        bool c = w >> i & 1;
        if (ch[x][c] && siz[ch[x][c]] - siz[ch[pre][c]] > 0)x = ch[x][c], pre = ch[pre][c];
        else ans = ans | 1 << i, x = ch[x][c ^ 1], pre = ch[pre][c ^ 1];
    }
    return make_pair(ans, tail[x]);
}
signed main() {
    re n = read<int>(), flag;
    ll ans = 0;
    for (re i = 1; i <= n; i++)a[i] = read<int>();
    sort(a + 1, a + 1 + n), n = unique(a + 1, a + 1 + n) - a - 1;
    for (re i = 1; i <= n; i++) insert(root[0], 30, i, a[i]), insert(root[i], 30, i, a[i]);
    while (1) {
        memset(minn, 0x3f, sizeof(minn)), flag = 0;
        for (re i = 1; i <= n; i++) {
            re x = find(i), y, w;
            pair<int, int> ret = query(root[0], root[x], a[i]);
            y = find(ret.second), w = ret.first;
            if (x != y) {
                if (w < minn[x])minn[x] = w, nxt[x] = y;
                if (w < minn[y])minn[y] = w, nxt[y] = x;
            }
        }
        for (re i = 1; i <= n; i++) {
            if (minn[i] < inf&&find(i) != find(nxt[i])) {
                ans += minn[i], flag = 1, merge(root[find(i)], root[find(nxt[i])]), fa[find(nxt[i])] = find(i);
            }
        }
        if (!flag)break;
    }
    writeln(ans);
}