两道神奇的字典树

lc0802 / 2024-03-22 / 原文

AEC122D

题意：你现在有 $2N$ 个球，现在 A 和 B 轮流拿，设每一次拿到两个球的权值的异或为 $p_i$，定义分数为 $\max \{ p_i\}$。A 希望它大，B 希望它小。求最后的分数。

题解：首先，B 有绝对优势，B 先把它们两两分组，A 拿走了一个时，B 直接拿走与它同组的那个。所以现在题目变为求每一组的异或的最小值。

现在把他们插入到字典树上。定义二进制 $i$ 位为 $v$ 的集合为 $S_v$。$(v = \{0, 1 \})$。定义 $S = S_0 \cup S_1$。（这里省略了 $i$，下同）

现在已知 $|S|=2n \in \text{even}$。所以 $S_0$ 和 $S_1$ 同奇偶。考虑按位贪心。

若它们都是偶数，那么这一位为 $0$，否则不优。递归为两个子问题。

否则，这一位无论如何我都为 $1$，那么第 $i$ 位以后的贡献为：

\[\mathop{\max}_{i \in S_0, j \in S_1} \{a_i \oplus a_j\} \]

用字典树维护即可。

AEC122D 的神奇加强版

题意：你现在有 $2N + 1$ 个球，提前拿出一个球 $k$。现在 A 和 B 轮流拿，设每一次拿到两个球的权值的异或为 $p_i$，定义分数为 $\max \{ p_i\}$。A 希望它大，B 希望它小。求每个 $k$ 最后的分数。对于所有数据，保证 $1\le n\le 2×10^5，0\le a_i < 2^{30}$。时间 $1$ 秒，空间 $64 \space \text{MiB}$。

同时维护 $2N+1$ 个数。则 $|S|=2n \in \text{odd}$。考虑当前状态下删掉 $k$ 这个球对第 $k$ 个答案的贡献。

那么，设 $O = (S_0 \cup \text{odd}) \cap (S_1 \cup \text{odd})$。$E = (S_0 \cup \text{even}) \cap (S_1 \cup \text{even})$。

当 $k \in O$ 时，两个都变成了偶数，此时奇数那一组就变成一个子问题，但是需要求解偶数那一组的答案，对奇数组的答案进行更新。

当 $k \in E$ 时，就变为两组奇数个，把奇数那一组插入 Trie，然后只需枚举偶数那一组的每个数，求出最小的配对之后取最小值或者次小值即可。

具体的，出题人比较卡时间或空间。考验良好的代码习惯。我是不用卡的，算法过了就过了。

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;

int n, dl, dr, midtmp, ls[10000005], rs[10000005], totcnt, u2;
long long ans1[N], ans2[N], resnow, now, tmp;
pair<int, int> a[N];
struct tri{long long fir, sec; int pos;}res, tmp2;

tri calXor(long long k, int l1, int r1, int l2, int r2, int u){
	res.fir = 1e18, res.sec = 1e18, res.pos = 0;
	for(int i = l1; i <= r1; i++){
		dl = l2, dr = r2, resnow = 0, u2 = u;
		for(int j = k; j >= 0; j--){
			now = (a[i].first >> j) & 1;
			if(!now && !ls[u2]) resnow += (1 << j), u2 = rs[u2];
			else if(!now) u2 = ls[u2];
			if(now && !rs[u2]) resnow += (1 << j), u2 = ls[u2];
			else if(now) u2 = rs[u2];
		}
		if(resnow <= res.fir)
			res.sec = res.fir, res.fir = resnow, res.pos = i;
		else if(res.sec >= resnow && resnow > res.fir)
			res.sec = resnow;
		resnow = 0;
	}
	return res;
}

long long calEven(long long k, int l, int r, int u){
	if(k < 0 || r - l + 1 <= 0) return 0;
	int mid = l;
	while(mid <= r && ((a[mid].first >> k) & 1) == 0) mid++;
	mid--;
	if((l - mid + 1) & 1) return (1 << k) + calXor(k - 1, l, mid, mid + 1, r, rs[u]).fir;
	return max(calEven(k - 1, l, mid, ls[u]), calEven(k - 1, mid + 1, r, rs[u]));
}

void calOdd(long long k, int l, int r, int u){
	if(k < 0 || (r - l + 1) < 0) return ;
	int mid = l;
	while(mid <= r && ((a[mid].first >> k) & 1) == 0) mid++;
	mid--;
	if((mid - l + 1) & 1){
		tmp = calEven(k - 1, mid + 1, r, rs[u]);
		for(int i = l; i <= mid; i++) ans2[i] = max(ans2[i], tmp);
		tmp2 = calXor(k - 1, mid + 1, r, l, mid, ls[u]);
		for(int i = mid + 1; i <= r; i++) ans1[i] += (1 << k);
		for(int i = mid + 1; i <= r; i++){
			if(i == tmp2.pos) ans1[i] += tmp2.sec;
			else ans1[i] += tmp2.fir;
		}
		
		calOdd(k - 1, l, mid, ls[u]);
	}
	else{
		tmp = calEven(k - 1, l, mid, ls[u]);
		for(int i = mid + 1; i <= r; i++) ans2[i] = max(ans2[i], tmp);
		tmp2 = calXor(k - 1, l, mid, mid + 1, r, rs[u]);
		for(int i = l; i <= mid; i++) ans1[i] += (1 << k);
		for(int i = l; i <= mid; i++){
			if(i == tmp2.pos) ans1[i] += tmp2.sec;
			else ans1[i] += tmp2.fir;
		}
		
		calOdd(k - 1, mid + 1, r, rs[u]);
	}
	return ;
}

void init(int l, int r, int k, int u){
	if(k < 0) return ;
	int mid = l;
	while(mid <= r && ((a[mid].first >> k) & 1) == 0) mid++;
	mid--;
	if(l <= mid) ls[u] = ++totcnt, init(l, mid, k - 1, totcnt);
	if(mid + 1 <= r) rs[u] = ++totcnt, init(mid + 1, r, k - 1, totcnt);
	return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	n = 2 * n + 1;
	for(int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
	sort(a + 1, a + 1 + n);
	
	totcnt = 1, init(1, n, 29, 1);
	calOdd(29, 1, n, 1);
	
	for(int i = 1; i <= n; i++) a[a[i].second].first = max(ans1[i], ans2[i]);
	for(int i = 1; i <= n; i++) cout << a[i].first << " ";
	return 0;
}