Untitled
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