Advertisement
Fahim_7861

trie on bit

Aug 13th, 2021
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef int ll;
  4. typedef unsigned long long ull;
  5. typedef pair<int,int>pii;
  6. typedef pair<ll,pair<ll,ll>>plll;
  7. #define sf(a) scanf("%I64d",&a)
  8. #define pf(a) printf("%I64d\n",a)
  9. #define mem(a,b) memset(a,b,sizeof(a))
  10. #define vll(v) v.begin(),v.end()
  11. #define all(x) x.rbegin(),x.rend()
  12. #define F first
  13. #define S second
  14. #define minheap int,vector<int>,greater<int>
  15. //#define mp make_pair
  16. #define pb push_back
  17. #define pp pop_back
  18. #define BOUNDARY(i, j) ((i >= 0 && i < row) && (j >= 0 && j < column))
  19. #define ischar(x) (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
  20. #define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
  21. #define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
  22. #define in freopen("input.txt", "r", stdin)
  23. #define out freopen("output.txt", "w", stdout)
  24. const int Max_node = 6e6 + 10;
  25. const int Mod = 1e9 + 7;
  26. bool compare(const pair<int,int> &a, const pair<int,int> &b)
  27. {
  28. return (a.first > b.first);
  29. }
  30. ll lcm(ll a,ll b)
  31. {
  32. if(a==0 || b==0)
  33. return 0;
  34.  
  35. return a/__gcd(a,b)*b;
  36. }
  37. //___________________________________________________________________________________________________________________
  38. // CODE STARTS FROM HERE
  39. // MU_Codefighter2018
  40. //-------------------------------------------------------------------------------------------------------------------
  41.  
  42.  
  43.  
  44. int root,nnode;
  45. int node[Max_node][2];
  46. ll cnt[Max_node];
  47.  
  48. void initialize()
  49. {
  50. root=0;
  51. nnode=0;
  52. memset(node,-1,sizeof(node));
  53. }
  54.  
  55.  
  56. void Insert(ll x)
  57. {
  58.  
  59. int now=0,i;
  60.  
  61. for(i=31; i>=0; i--)
  62. {
  63. ll bit=(x>>i)&1;
  64.  
  65. if(node[now][bit]==-1)
  66. node[now][bit]=++nnode;
  67.  
  68.  
  69. now=node[now][bit];
  70.  
  71. cnt[now]++;
  72. }
  73. }
  74.  
  75. void Delete(ll x)
  76. {
  77. int now=0,i;
  78.  
  79. for(i=31; i>=0; i--)
  80. {
  81. ll bit=(x>>i)&1;
  82.  
  83.  
  84. now=node[now][bit];
  85.  
  86. cnt[now]--;
  87. }
  88. }
  89.  
  90.  
  91.  
  92. ll query(ll x)
  93. {
  94. root=0;
  95. int now=root,i,ans=0;
  96.  
  97. for(i=31; i>=0; i--)
  98. {
  99. ll bit=(x>>i)&1;
  100.  
  101. if(cnt[node[now][!bit]]>0)
  102. {
  103. ans|=(1<<i); // ANS jodi long long hoy tahole 1LL<<i aibabay liktay hobe
  104.  
  105. now=node[now][!bit];
  106.  
  107. }
  108. else now=node[now][bit];
  109.  
  110.  
  111.  
  112.  
  113.  
  114. }
  115.  
  116. return ans;
  117. }
  118.  
  119. int main()
  120. {
  121. fastread();
  122. initialize();
  123.  
  124. ll t;
  125.  
  126.  
  127.  
  128. cin>>t;
  129.  
  130. char ch;
  131.  
  132. ll x;
  133.  
  134. Insert(0);
  135.  
  136. while(t--)
  137. {
  138. cin>>ch>>x;
  139.  
  140. switch(ch)
  141. {
  142. case '+' : Insert(x);
  143.  
  144. break;
  145.  
  146. case '-' : Delete(x);
  147.  
  148. break;
  149.  
  150. case '?' :
  151. {
  152. x=query(x);
  153. cout<<x<<endl;
  154. }
  155. }
  156. }
  157.  
  158.  
  159.  
  160.  
  161. }
  162.  
  163.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement