写的是较为好写的分治写法，求出 $n \log n$ 条边后跑 Kruscal ，有没有大佬能解释一下这个的正确性，顺便问下为什么我 $a$ 数组没排序的过不去。

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define drep(i, x, y) for (int i = x; i >= y; --i)
#define ll long long
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 200020;
struct edge {
	int u, v, w;
} E[N * 40];
int n, cnt, idx, fa[N], a[N], t[N * 30][2], id[N * 30];
int find(int x) {
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
inline void Up(int &p) {
	if(!p) {
		p = ++idx;
		t[p][0] = t[p][1] = 0;
	}
}
inline void clear() {
	idx = 1;
	t[1][0] = t[1][1] = 0;
}
inline void ins(int x, int i) {
	int p = 1;
	drep(i, 29, 0) {
		int c = (x >> i) & 1;
		Up(t[p][c]);
		p = t[p][c];
	}
	id[p] = i;
}
inline int qry(int x) {
	int p = 1;
	drep(i, 29, 0) {
		int c = (x >> i) & 1;
		if(t[p][c]) p = t[p][c];
		else p = t[p][c ^ 1];
	}
	return id[p];
}
void solve(int l, int r) {
	if(l == r) return;
	int mid = (l + r) >> 1;
	solve(l, mid), solve(mid + 1, r);
	clear();
	rep(i, l, mid) ins(a[i], i);
	rep(i, mid + 1, r) {
		int j = qry(a[i]); assert(j);
		E[++cnt] = {i, j, a[i] ^ a[j]};
	}
	clear();
	rep(i, mid + 1, r) ins(a[i], i);
	rep(i, l, mid) {
		int j = qry(a[i]); assert(j);
		E[++cnt] = {i, j, a[i] ^ a[j]};
	}
}
bool merge(int x, int y) {
	x = find(x), y = find(y);
	if(x == y) return 0;
	fa[x] = y; return 1;
}
int main() {
	IOS;
	cin >> n; rep(i, 1, n) cin >> a[i];
	sort(a + 1, a + 1 + n);
	ll res = 0; rep(i, 1, n) fa[i] = i; solve(1, n);
	sort(E + 1, E + 1 + cnt, [&](edge x, edge y) { return x.w < y.w; });
	rep(i, 1, cnt) if(merge(E[i].u, E[i].v)) res += E[i].w;
	cout << res << '\n';
	return 0;
}