lessons/参考实现/06-最小与最大生成树/CodeForces-888G.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end());

    auto solve = [&](auto &&self, int left, int right, int bit) -> long long {
        if (right - left <= 1 || bit < 0) return 0;
        int middle = left;
        while (middle < right && ((a[middle] >> bit) & 1) == 0) ++middle;
        long long answer = self(self, left, middle, bit - 1) + self(self, middle, right, bit - 1);
        if (middle == left || middle == right) return answer;

        int build_l = left, build_r = middle, query_l = middle, query_r = right;
        if (build_r - build_l > query_r - query_l) {
            swap(build_l, query_l); swap(build_r, query_r);
        }
        vector<array<int, 2>> trie(1, array<int, 2>{-1, -1});
        trie.reserve(static_cast<size_t>(build_r - build_l) * (bit + 1) + 1);
        for (int i = build_l; i < build_r; ++i) {
            int node = 0;
            for (int b = bit - 1; b >= 0; --b) {
                int digit = (a[i] >> b) & 1;
                if (trie[node][digit] == -1) {
                    trie[node][digit] = static_cast<int>(trie.size());
                    trie.push_back({-1, -1});
                }
                node = trie[node][digit];
            }
        }
        int best = numeric_limits<int>::max();
        for (int i = query_l; i < query_r; ++i) {
            int node = 0, cost = 0;
            for (int b = bit - 1; b >= 0; --b) {
                int digit = (a[i] >> b) & 1;
                if (trie[node][digit] != -1) node = trie[node][digit];
                else cost |= 1 << b, node = trie[node][digit ^ 1];
            }
            best = min(best, cost);
        }
        return answer + (1LL << bit) + best;
    };
    cout << solve(solve, 0, static_cast<int>(a.size()), 29) << '\n';
}