Rudro_Debnath

Untitled

May 13th, 2021
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define PSB push_back
  5. #define MP make_pair
  6. #define ll long long
  7. #define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  8. constexpr ll mod = 1e9 + 7;
  9. const ll N=3e6+5;
  10. const ll INF =1e18;
  11.  
  12. int prefix_count;
  13. bool check;
  14. vector<ll> vv,v;
  15.  
  16. struct node {
  17. bool endmark;
  18. int count;
  19. node* next[2];
  20. node()
  21. {
  22. endmark = false;
  23. count=0;
  24. for (int i = 0; i < 2; i++)
  25. next[i] = NULL;
  26. }
  27. } * root;
  28. void insert(int len)
  29. {
  30. node* curr = root;
  31. int kount=0;
  32. for (int i = 0; i < len; i++) {
  33. int id = v[i];
  34. if (curr->next[id] == NULL)
  35. curr->next[id] = new node();
  36. curr = curr->next[id];
  37. ++ curr->count ; // count no of words with prefix till curr
  38. }
  39. //curr->endmark = true;
  40. }
  41. void search(int len)
  42. {
  43. node* curr = root;
  44. vv.clear();
  45. for (int i = 0; i < len; i++) {
  46. int id = (v[i]^1LL);
  47. if (curr->next[id] == NULL)
  48. id= (id ^ 1LL);
  49. curr = curr->next[id];
  50. if(id==v[i]) vv.PSB(0);
  51. else vv.PSB(1);
  52. }
  53. reverse(vv.begin(),vv.end());
  54. ll ct=1,ans=0;
  55. for(ll i=0;i<vv.size();i++){
  56. ans+=ct*vv[i];
  57. ct*=2LL;
  58. }
  59. cout<<ans<<endl;
  60. //if(curr->endmark) check= true;
  61. //prefix_count= curr->count; // count no of prefix in the trie for str
  62. //return curr->endmark; //full word tai actually ase kina check kore
  63. //return true; // eta krle prefix hishabe paile true bolbe
  64. }
  65. void del_full_trie(node* cur)
  66. {
  67. for (int i = 0; i < 2; i++)
  68. if (cur->next[i])
  69. del_full_trie(cur->next[i]);
  70.  
  71. delete (cur);
  72. }
  73. void del(int len)
  74. {
  75. node* curr = root;
  76. bool ck=false;
  77. for (int i = 0; i < len; i++) {
  78. int id = v[i],pre;
  79. if((curr->next[id])->count==1){
  80. curr->next[id]=NULL;
  81. curr = curr->next[id];
  82. del_full_trie(curr);
  83. break;
  84. }
  85. curr = curr->next[id];
  86. ll x= -- curr->count ; // count no of words with prefix till curr
  87. //cout<<id<<' '<<x<<endl;
  88. }
  89. }
  90.  
  91. int main()
  92. {
  93.  
  94. //first time trying trie
  95. root = new node();
  96. for(ll j=0;j<32;j++)
  97. v.PSB(0);
  98. insert(v.size());
  99.  
  100. ll n; cin>>n;
  101. for(ll i=0;i<n;i++){
  102. char ch; ll x;
  103. cin>>ch>>x;
  104. v.clear();
  105. for(ll j=0;j<32;j++){
  106. if(x%2) v.PSB(1);
  107. else v.PSB(0);
  108. x>>=1;
  109. }
  110. reverse(v.begin(),v.end());
  111. if(ch=='+') insert(v.size());
  112. else if(ch=='-') del(v.size());
  113. else search(v.size());
  114. }
  115. del_full_trie(root); //killed the trie
  116. return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment