cf888G. Xor-MST(Boruvka最小生成树 Trie树)

题意

题目链接

给出\(n\)点，每个点有一个点权\(a[i]\)，相邻两点之间的边权为\(a[i] \oplus a[j]\)，求最小生成树的值

Sol

非常interesting的一道题，我做过两种这类题目，一种是直接打表找规律，另一种就像这种用Boruvka算法加一些骚操作来搞。

首先，把所有元素扔到Trie树里面，这样对于Trie树上的每一层(对应元素中的每一位)共有两种情况:

1. 全为0或全为1

2. 一部分为0另一部分为1

对于第一种情况，我们无需考虑，因为任意点相邻产生的贡献都是0，对于第二种情况，需要找到一条最小的边来连接链各个集合，这可以在Trie树上贪心实现

另外还有一个小Trick，我们把元素从小到大排序，这样Trie树上每个节点对应的区间就都是连续的

实现的时候可以从底往上update，也可以从上往下dfs

时间复杂度：\(O(nlognlog_{max(a_i)})\)

本来以为这题要写一年，结果写+调只用了1h不到？

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define fi first

#define se second

#define MP(x, y) make_pair(x, y)

#define LL long long

using namespace std;

const int MAXN = 2e5 + 10, B = 31, INF = 1e9 + 7;

inline LL read() {

    char c = getchar(); LL x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, a[MAXN], L[MAXN * 30], R[MAXN * 30], ch[MAXN * 30][2], tot = 0;

void insert(int val, int pos) {

	int now = 0;

	for(int i = B; ~i; i--) {

		int x = val >> i & 1;

		if(!ch[now][x]) ch[now][x] = ++tot, L[tot] = pos, R[tot] = pos;//???ʵ???֮?????λ

		L[now] = min(L[now], pos); R[now] = max(R[now], pos);

		now = ch[now][x];

	}

}

int Query(int val, int now, int NowBit) {

	LL ans = 1 << (NowBit + 1);

	for(int i = NowBit; ~i; i--) {

		int x = val >> i & 1;

		if(ch[now][x]) now = ch[now][x];

		else ans |= 1 << i, now = ch[now][x ^ 1];

	}

	return ans;

}

LL dfs(int x, int NowBit) {

	LL res = 0;

	if(NowBit == 0)

		return (ch[x][0] && ch[x][1]) ? (a[L[ch[x][0]]] ^ a[R[ch[x][1]]]) : 0;

	//if(NowBit == 0) return ;

	if(ch[x][0] && ch[x][1]) {

		int tmp = INF;

		for(int i = L[ch[x][0]]; i <= R[ch[x][0]]; i++) tmp = min(tmp, Query(a[i], ch[x][1], NowBit - 1));

		res += tmp;

	}

	if(ch[x][0]) res += dfs(ch[x][0], NowBit - 1);

	if(ch[x][1]) res += dfs(ch[x][1], NowBit - 1);

	return res;

}

int main() {

	N = read();

	for(int i = 1; i <= N; i++) a[i] = read();

	sort(a + 1, a + N + 1);

	L[0] = INF; R[0] = 0;

	for(int i = 1; i <= N; i++) insert(a[i], i);

	cout << dfs(0, B);

    return 0;

}