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;
}