AcDream 1081 平衡树 Tire树

题意：有这样的一个需求，一个程序能够动态的插入数字，并且能够以很快的速度给出一个数字在已有的数字集合中异或之后值的最大或者是最小值。

解法：将插入的数构成一棵字典树，然后将每一个数字以贪心的思想去匹配，如果一个数字为1010，要求与它异或之后值的最小值，只需要在为1的地方优先匹配1，为0的地方优先匹配0；如果是求最大值就把这个数字进行取反操作，然后找出一个数与取反之后的数异或值最小即可。

代码如下：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstring>
using namespace std;

int mask[32], idx;

struct Node {
    int ch[2];
    int val;
    void init() {
        ch[0] = ch[1] = val = -1;
    }
}e[32*10005];

void pre() {
    for (int i = 0; i < 31; ++i) {
        mask[i] = 1 << i;
    } // 使用mask就能够用来快速求出某一位是否为1 
}

void insert(int p, int lev, int val) {
    if (lev == -1) {
        e[p].val = val;
        return;
    }
    bool r = val & mask[lev]; // 指出是否为1
    if (e[p].ch[r] == -1) {
        e[idx].init();
        e[p].ch[r] = idx++; // 为分支分配一个新的节点 
    }
    insert(e[p].ch[r], lev-1, val);
}

int search(int p, int lev, int val) {
    if (lev == -1) {
        return e[p].val;
    }
    bool r = val & mask[lev];
    if (e[p].ch[r] != -1) {
        return search(e[p].ch[r], lev-1, val);    
    } else {
        return search(e[p].ch[!r], lev-1, val);    
    }
}

int main() {
    pre();
    int T, N, x;
    char op[15];
    scanf("%d", &T);
    while (T--) {
        e[0].init();
        idx = 1; // 根节点已经占用了一个位置
        scanf("%d", &N);
        while (N--) {
            scanf("%s %d", op, &x);
            if (op[0] == 'i') { // 插入 
                insert(0, 30, x); // 从第31位数开始构造起
            } else if (op[2] == 'i'){ // 求最小值
                printf("%d\n", x ^ search(0, 30, x));
            } else { // 求最大值
                printf("%d\n", x ^ search(0, 30, ~x));
            }
        }
    }
    return 0;
}