#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; // 加上边权
}
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
我的理解写在注释里面,请问哪里不太准确,还有最开始对点权排序的操作有什么必要性