The XOR Largest Pair(tire樹)

題目

The XOR Largest Pair

解析

一年前聽學長講這道題，什麼01trie，好高級啊，所以沒學，現在一看。。。。
看到xor就應該想到二進位，一看數據\(A_i< 2^{31}\)，考慮把所有的數都處理成長度為32的二進位數，插入字典樹中，查詢的時候就逐位比較，有不同的先走不同的那邊，這樣保證了每次插入一個數時查詢的結果是最大的，然後不斷更新最大值就可以了
我這種不用位運算的懶人就直接用bitset維護了
從高位到地位插入可能好算一些

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 10;

int n, a, num, ans;

struct node {
    int nx[2];
} e[N];

void insert(int n) {
    bitset<35>s(n);
    int rt = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)s[i];
        if (!e[rt].nx[v]) e[rt].nx[v] = ++num;
        rt = e[rt].nx[v];
    }
}

int query(int x) {
    bitset<35>s(x);
    int rt = 0, ret = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)s[i];
        if (e[rt].nx[v ^ 1]) ret = ret << 1 | 1, rt = e[rt].nx[v ^ 1];
        else ret <<= 1, rt = e[rt].nx[v];
    }
    return ret;  
}

int main() {
    cin >> n;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        ans = max(ans, query(x));
        insert(x);
    }
    cout << ans;
}