#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 2e5 + 7;
const int BITS = 30;
int trieNodeCount, trie[MAXN*BITS][2], maxIndex[MAXN*BITS];
int numNodes, nodeValues[MAXN];

void insert(int value, int index) {	// 建字典树 
	int currentNode = 0;
	for(int bit = BITS - 1; bit >= 0; bit --) {
		int currentBit = (value >> bit) & 1;
		if (!trie[currentNode][currentBit]) {
			trie[currentNode][currentBit] = trieNodeCount ++;
		}
		currentNode = trie[currentNode][currentBit];
		// 对于多个相同的点，找出编号最大的一个点，即右端点 
		maxIndex[currentNode] = max(maxIndex[currentNode], index);
	}
}

int query(int value, int index) {  // 查询所有点权中与传入点权亦或最小值 
	int currentNode = 0, result = 0;
	for (int bit = BITS - 1; bit >= 0; bit --) {  // 从高位向低位枚举 
		int currentBit = (value >> bit) & 1;	// 取出当前位
		// 1.当前位下仍有孩子 
		// 2.对于当前位相同的编号最大的点 如果大于给出的编号，则使用当前点 
		if (trie[currentNode][currentBit] && maxIndex[trie[currentNode][currentBit]] >= index) {
			currentNode = trie[currentNode][currentBit];
		} else {
			currentNode = trie[currentNode][currentBit ^ 1];
			result += (1 << bit);  // 这里没有太明白 
		}
	}
	return result; 
}

ll weight = 0;
void findMinimumXor(int left, int right, int bitPosition) {  // 字典树上的一段区间左右，以及当前查找的位 
	if (left == right || bitPosition < 0) return;
	int mid = left;
	while (mid < right && !((nodeValues[mid] >> bitPosition) & 1)) mid ++;
	// 找到这样一个 mid，使得在 bitPosition 位上，left ~ mid - 1 为 0，mid ~ right 为 1 
	findMinimumXor(left, mid, bitPosition - 1);  // 分治 
	findMinimumXor(mid, right, bitPosition - 1);
	if (mid == right || mid == left) return;  // 如果全为 0 或全为 1 
	int minEdgeWeight = INT_MAX;  // 最小边权 
	for (int i = left; i < mid; i++)  // 在较小的左区间内遍历，与右区间内最小的点权(mid)取亦或最小值 
		minEdgeWeight = min(minEdgeWeight, query(nodeValues[i], mid));
	weight += minEdgeWeight;  // 加上边权
	/* 
	当前的理解是 : 
	对于 left ~ mid - 1 和 mid ~ right 两个子区间已经分治求出了联通块内部的最小生成树，
	那么连接这两个联通块的最小边权的边就是最小生成树中的一条边 
	现在不清楚为什么要这么寻找 
	*/ 
}

int main() {
	trieNodeCount = 1;  // 字典树节点个数初始化为 1 
	cin >> numNodes;	// 点的个数 
	for (int i = 0; i < numNodes; i++) cin >> nodeValues[i];  // 读入点权 
	sort(nodeValues, nodeValues + numNodes);  // 对点权从小到大排序 
	for (int i = 0; i < numNodes; i++) insert(nodeValues[i], i);   // 对所有点建立 0/1 trie 
	findMinimumXor(0, numNodes, BITS - 1);  // 找到最小生成树 
	cout << weight << endl;
	return 0;
}

// CF888G

这是初赛模拟题上的一道阅读程序，原题在CF888G

我把我的理解写在注释里面，想问一下有哪些不对的地方，以及一开始的对点权排序的必要性是什么