Dang_Quan_10_Tin

TRIE

Jul 23rd, 2020
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #define NguyenDangQuan the_author
  2. #define my_heart love_you_to_the_moon_and_back
  3.  
  4. #include <bits/stdc++.h>
  5. #define pb push_back
  6. #define ld long double
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define float double
  10. using namespace std;
  11.  
  12. int typetest;
  13. inline void fastIOfileinput(){
  14.     ios::sync_with_stdio(0);
  15.     cin.tie(0);
  16.     cout.tie(0);
  17.     typetest = 0;
  18. }
  19.  
  20. struct trie{
  21.     trie *child[2];
  22.     int v;
  23.     void upd(int id, int lim, int u, int x, int val){
  24.         //cerr << lim << " ";
  25.         if(id == lim){
  26.             v += val;
  27.             return;
  28.         }
  29.         if(child[(x >> id) & 1] == nullptr)
  30.             child[(x >> id) & 1] = new trie,
  31.             child[(x >> id) & 1] -> v = 0;
  32.         child[(x >> id) & 1] -> upd(id + u, lim, u, x, val);
  33.         if(child[(x >> id) & 1] -> v == 0){
  34.             delete child[(x >> id) & 1];
  35.             child[(x >> id) & 1] = nullptr;
  36.         }
  37.         v += val;
  38.     }
  39.  
  40. };
  41.  
  42. const int N = 5e4 + 3;
  43. int n, m;
  44. vector<int> adj[N];
  45. int par[N];
  46. char t;
  47. int x, ans;
  48. trie began;
  49.  
  50. void Enter(){
  51.     cin >> m;
  52.     began.child[1] = began.child[0] = nullptr;
  53.     began.upd(30, -1, -1, 0, 1);
  54. }
  55.  
  56. void check(trie &a, int id, int lim, int upd, int x){
  57.     if(id == lim)
  58.         return;
  59.     if(a.child[!((x >> id) & 1)] != nullptr){
  60.         ans |= 1 << id;
  61.         check(*a.child[!((x >> id) & 1)], id + upd, lim, upd, x);
  62.     }
  63.     else
  64.         check(*a.child[(x >> id) & 1], id + upd, lim, upd, x);
  65. }
  66.  
  67. void solve(){
  68.     while(m--){
  69.         cin >> t >> x;
  70.         if(t == '+')
  71.             began.upd(30, -1, -1, x, 1);
  72.         else if(t == '-')
  73.             began.upd(30, -1, -1, x, -1);
  74.         else{
  75.             ans = 0;
  76.             check(began, 30, -1, -1, x);
  77.             cout << ans << "\n";
  78.         }
  79.     }
  80. }
  81.  
  82. main(){
  83.     fastIOfileinput();
  84.     if(typetest){
  85.         int t;
  86.         cin >> t;
  87.         while(t--){
  88.             Enter();
  89.             solve();
  90.         }
  91.     }
  92.     else{
  93.         Enter();
  94.         solve();
  95.     }
  96. }
Advertisement
Add Comment
Please, Sign In to add comment