CFR 706 D. Vasiliy's Multiset ( XOR Trie )

Problem - D - Codeforces
經典的 XOR Trie，沒什麼好說的。
這次的題目都好簡單，要不是那天有SAT模考就能大賺一波rating了...

struct Trie{
    Trie *ch[ 2 ];
    int cnt;
    Trie(){
        ch[ 0 ] = ch[ 1 ] = NULL;
        cnt = 0;
    }
    void add( int v, int k ){
        if( k < 0 ) return;
        int g = v >> k & 1;
        if( ch[ g ] == NULL ) ch[ g ] = new Trie();
        ++ch[ g ]->cnt;
        ch[ g ]->add( v, k - 1 );
    }
    void erase( int v, int k ){
        if( k < 0 ) return;
        int g = v >> k & 1;
        if( ch[ g ] == NULL ) ch[ g ] = new Trie();
        --ch[ g ]->cnt;
        ch[ g ]->erase( v, k - 1 );
    }
    void get_max_xor( int v, int k, int &res ){
        if( k < 0 ) return;
        res <<= 1;
        int g = v >> k & 1;
        if( ch[ g ^ 1 ] and ch[ g ^ 1 ]->cnt ) ch[ g ^ 1 ]->get_max_xor( v, k - 1, res |= 1 );
        else ch[ g ]->get_max_xor( v, k - 1, res );
    }
};

void solve(){
    Trie *root = new Trie();
    root->add( 0, 30 );
    int Q; cin >> Q;
    for( int i = 0; i < Q; ++i ){
        string op; cin >> op;
        int x; cin >> x;
        if( op == "+" ){
            root->add( x, 30 );
        } else if( op == "-" ){
            root->erase( x, 30 );
        } else{
            int ans = 0;
            root->get_max_xor( x, 30, ans );
            cout << ans << "\n";
        }
    }
}