Salvens

C

Aug 10th, 2023
875
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8. #include <set>
  9. #include <cassert>
  10. #include <bitset>
  11.  
  12.  
  13. using namespace std;
  14.  
  15. #define int long long
  16. #pragma comment(linker,"/STACK:1000000000,1000000000")
  17.  
  18. const long long INF = 1e9 + 7;
  19. const int MAXN = 2e5 * 32 + 100;
  20. const int N = 1e5 + 10;
  21.  
  22. struct vertex {
  23.     int next[3];
  24.     int terminal = 0;
  25. } v[MAXN];
  26.  
  27. array<int, MAXN> kol;
  28.  
  29. int root = 0, top = 1;
  30.  
  31. inline void add(int num) {
  32.     int cur = root;
  33.     bitset<32> a(num);
  34.     for (int i = 31; i >= 0; --i) {
  35.         if (v[cur].next[a[i]] == 0) {
  36.             v[cur].next[a[i]] = top++;
  37.         }
  38.         ++kol[cur];
  39.         cur = v[cur].next[a[i]];
  40.     }
  41.     ++kol[cur];
  42.     v[cur].terminal = num;
  43. }
  44.  
  45. inline void del(int num) {
  46.     int cur = root;
  47.     bitset<32> a(num);
  48.     for (int i = 31; i >= 0; --i) {
  49.         --kol[cur];
  50.         cur = v[cur].next[a[i]];
  51.     }
  52.     --kol[cur];
  53.     v[cur].terminal = 0;
  54. }
  55.  
  56. inline int get(int num) {
  57.     int cur = root;
  58.     bitset<32> a(num);
  59.     int res = 0;
  60.     for (int i = 31; i >= 0; --i) {
  61.         if (v[cur].next[!a[i]] != 0 && kol[v[cur].next[!a[i]]]) {
  62.             cur = v[cur].next[!a[i]];
  63.             res |= 1 << i;
  64.         } else {
  65.             cur = v[cur].next[a[i]];
  66.         }
  67.     }
  68.     return res;
  69. }
  70.  
  71. signed main() {
  72.     ios_base::sync_with_stdio(false);
  73.     cin.tie(nullptr);
  74.     cout.tie(nullptr);
  75.  
  76.     add(0);
  77.  
  78.     int q;
  79.     cin >> q;
  80.     while (q--) {
  81.         char type;
  82.         int x;
  83.         cin >> type >> x;
  84.         if (type == '+') {
  85.             add(x);
  86.         } else if (type == '-') {
  87.             del(x);
  88.         } else if (type == '?') {
  89.             cout << get(x) << '\n';
  90.         }
  91.     }
  92. }
Advertisement
Add Comment
Please, Sign In to add comment