记录编号	601357	评测结果	AAAAAAAAAA
题目名称	4062.Xor-MST	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	19.710 s
提交时间	2025-06-16 21:02:08	内存使用	153.83 MiB

#include<bits/stdc++.h>
using namespace std;
// #define LOCAL
#define ll long long
#define pir pair <ll,ll>
#define fs first
#define sc second
#define MAXN 200010
#define ls(x) son[x][0]
#define rs(x) son[x][1]
inline ll read(){
    ll f = 1, num = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c=='-') f = -1;c = getchar();
    }
    while(c>='0'&&c<='9') num = num * 10 + c - '0', c = getchar();
    return num * f;
}

int rt[MAXN];
struct node_trie{
    int son[MAXN * 50][2];
    int siz[MAXN * 50],id[MAXN * 50];
    int idx;

    int query(ll v, ll p){
        ll q = rt[0];
        for(int i = 30;i >= 0; --i){
            ll x = (v & (1ll << i)) ? 1 : 0;
            // cout << "query : p: " << p << " q: " << q << " ls: " << siz[son[q][x]] << " " << son[q][x ^ 1] << " " << siz[son[q][x ^ 1]] << " rs:" << siz[son[p][x]] << " " << v << " " << i << " " << x << " " << id[q] << endl;
            if(siz[son[q][x]] - siz[son[p][x]] > 0){
                p = son[p][x];
                q = son[q][x];
            }else{
                p = son[p][x ^ 1];
                q = son[q][x ^ 1];
            }
        }
        // cout << "query : " << q << " " << id[q] << endl;
        return id[q];
    }

    int merge(ll x, ll y){
        if(!x || !y)return x | y;
        siz[x] += siz[y];
        if(!id[x])id[x] = id[y];
        ls(x) = merge(ls(x), ls(y));
        rs(x) = merge(rs(x), rs(y));
        return x;
    }

    void insert(ll p, ll v, ll y){
        for(int i = 30;i >= 0; --i){
            ll x = (v & (1ll << i)) ? 1 : 0;
            if(son[p][x])p = son[p][x];
            else son[p][x] = ++idx, p = son[p][x];
            ++ siz[p];
        }
        // cout << "insert : " << p << " " << y << endl;
        id[p] = y;
    }
}trie;

set <ll> st;

struct node_dsu{
    int fa[MAXN];
    int cnt;
    int get(ll x){
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }

    void merge(ll x, ll y){
        x = get(x),y = get(y);
        if(x == y)return;
        fa[x] = y;
        -- cnt;
        st.erase(x);
        trie.merge(rt[y], rt[x]);
    }

    void init(ll x){
        cnt = x;
        rt[0] = ++ trie.idx;
        for(int i = 1;i <= x; ++i){
            fa[i] = i;
            rt[i] = ++ trie.idx;
            st.insert(i);
        }
    }
}dsu;

ll n,ans;
int a[MAXN],mn[MAXN],e[MAXN];
bool vis[MAXN];

int main(){
    #ifdef LOCAL
        freopen("w.in", "r", stdin);
        freopen("w.out", "w", stdout);
    #endif

    n = read();
    dsu.init(n);
    for(int i = 1;i <= n; ++i){
        a[i] = read();
        ll stp = trie.idx;
        trie.insert(rt[0], a[i], i);
        trie.insert(rt[i], a[i], i);
        // cout << trie.idx << " " << trie.idx - stp << endl;
    }

    while(dsu.cnt > 1){
        for(auto y : st)vis[y] = e[y] = 0,mn[y] = 1e9;

        // memset(vis, 0, sizeof(vis));
        // memset(mn, 0x3f, sizeof(mn));
        // memset(e, 0, sizeof(e));
        // cout << ans << " " << dsu.cnt << endl;

        for(int i = 1;i <= n; ++i){
            ll fi = dsu.get(i);
            ll y = trie.query(a[i], rt[fi]);
            if((a[i] ^ a[y]) < mn[fi]){
                // cout << i << " " << fi << " " << y << " " << (a[i] ^ a[y]) << endl;
                mn[fi] = a[i] ^ a[y];
                e[fi] = y;
            }
        }

        for(int i = 1;i <= n; ++i){
            ll fi = dsu.get(i);
            if(!vis[fi]){
                vis[fi] = true;
                if(dsu.get(fi) == dsu.get(e[fi]))continue;
                dsu.merge(fi, e[fi]);
                ans += mn[fi];
            }
        }
    }

    cout << ans << endl;

    // cerr << "Time : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";
    return 0;
}