Perfect Security（01字典树）

题目：

给 $n$ 个数 $A_1A_2 \dots A_n$ ，和 $n$ 个数 $P_1P_2 \dots P_n$ 。让你确定一个排列 $K$ ，使得序列 $A_1xorP_{K_1}\space A_2xorP_{K_2} \dots A_nxorP_{K_n}$ 。字典序最小。

做法：

其实是个贪心，每次从 $P$ 中剩下的数中选一个数 $X$ ，使 $A_ixorX$ 最小，然后 $P$ 中删去 $X$ 。最后得到的序列就是答案了。所以重点是 $01$ 字典树的删除操作该怎么写。我的做法是，每个叶子记录一个 $sze$ ，代表这个数的数量。每次删去一个数时，对应叶子结点的 $sze-1$ ，如果 $sze$ 变为 $0$ ，则删去该叶子，向上判断父亲结点是否变成了叶子，若是删去父亲，循环。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 3e5 + 7;
int a[N];
struct Trie{
    static const int N = 5e6 + 7;
    int tot, ch[N][2], fa[N], sze[N];
    void insert(int x){
        int now = 0;
        for (int i = 30; i >= 0; --i){
            int b = (x>>i)&1;
            if (!ch[now][b]) ch[now][b] = ++tot, fa[tot] = now;
            now = ch[now][b];
        }
        sze[now]++;
    }
    int ask(int x){
        int now = 0, ans = 0;
        for (int i = 30; i >= 0; --i){
            int b = (x>>i)&1;
            if (ch[now][b]) now = ch[now][b];
            else now = ch[now][b^1], ans |= (1<<i);
        }
        if ((--sze[now]) == 0){
            while (now){
                int f = fa[now], b = (ch[f][1] == now);
                ch[f][b] = 0;
                if (ch[f][b^1]) break;
                now = f;
            }
        }
        return ans;
    }
}trie;
int main(void){
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i){
        int x; cin >> x;
        trie.insert(x);
    } 
    for (int i = 1; i <= n; ++i){
        cout << trie.ask(a[i]) << ' ';
    }
    return 0;
}