Perfect Security（01字典树）

题目：

给个数，和个数。让你确定一个排列，使得序列。字典序最小。

做法：

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

代码：

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