Untitled

 avatar
unknown
c_cpp
a year ago
1.1 kB
4
Indexable
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 200000 * 30;

int trie[N][2];
int sum[N];
int cnt = 1;

void add(int x, int t) {
    int p = 1;
    sum[p] += t;
    for (int i = 29; i >= 0; i--) {
        int d = x >> i & 1;
        if (!trie[p][d]) {
            trie[p][d] = ++cnt;
        }
        p = trie[p][d];
        sum[p] += t;
    }
}

int query(int x) {
    int ans = 0;
    int p = 1;
    for (int i = 29; i >= 0; i--) {
        int d = x >> i & 1;
        if (sum[trie[p][!d]]) {
            p = trie[p][!d];
            ans |= 1 << i;
        } else {
            p = trie[p][d];
        }
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int q;
    std::cin >> q;
    
    add(0, 1);
    for (int i = 0; i < q; i++) {
        char t;
        int x;
        std::cin >> t >> x;
        
        if (t == '+') {
            add(x, 1);
        } else if (t == '-') {
            add(x, -1);
        } else {
            std::cout << query(x) << "\n";
        }
    }
    
    return 0;
}
Editor is loading...
Leave a Comment