Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define PSB push_back
- #define MP make_pair
- #define ll long long
- #define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
- constexpr ll mod = 1e9 + 7;
- const ll N=3e6+5;
- const ll INF =1e18;
- int prefix_count;
- bool check;
- vector<ll> vv,v;
- struct node {
- bool endmark;
- int count;
- node* next[2];
- node()
- {
- endmark = false;
- count=0;
- for (int i = 0; i < 2; i++)
- next[i] = NULL;
- }
- } * root;
- void insert(int len)
- {
- node* curr = root;
- int kount=0;
- for (int i = 0; i < len; i++) {
- int id = v[i];
- if (curr->next[id] == NULL)
- curr->next[id] = new node();
- curr = curr->next[id];
- ++ curr->count ; // count no of words with prefix till curr
- }
- //curr->endmark = true;
- }
- void search(int len)
- {
- node* curr = root;
- vv.clear();
- for (int i = 0; i < len; i++) {
- int id = (v[i]^1LL);
- if (curr->next[id] == NULL)
- id= (id ^ 1LL);
- curr = curr->next[id];
- if(id==v[i]) vv.PSB(0);
- else vv.PSB(1);
- }
- reverse(vv.begin(),vv.end());
- ll ct=1,ans=0;
- for(ll i=0;i<vv.size();i++){
- ans+=ct*vv[i];
- ct*=2LL;
- }
- cout<<ans<<endl;
- //if(curr->endmark) check= true;
- //prefix_count= curr->count; // count no of prefix in the trie for str
- //return curr->endmark; //full word tai actually ase kina check kore
- //return true; // eta krle prefix hishabe paile true bolbe
- }
- void del_full_trie(node* cur)
- {
- for (int i = 0; i < 2; i++)
- if (cur->next[i])
- del_full_trie(cur->next[i]);
- delete (cur);
- }
- void del(int len)
- {
- node* curr = root;
- bool ck=false;
- for (int i = 0; i < len; i++) {
- int id = v[i],pre;
- if((curr->next[id])->count==1){
- curr->next[id]=NULL;
- curr = curr->next[id];
- del_full_trie(curr);
- break;
- }
- curr = curr->next[id];
- ll x= -- curr->count ; // count no of words with prefix till curr
- //cout<<id<<' '<<x<<endl;
- }
- }
- int main()
- {
- //first time trying trie
- root = new node();
- for(ll j=0;j<32;j++)
- v.PSB(0);
- insert(v.size());
- ll n; cin>>n;
- for(ll i=0;i<n;i++){
- char ch; ll x;
- cin>>ch>>x;
- v.clear();
- for(ll j=0;j<32;j++){
- if(x%2) v.PSB(1);
- else v.PSB(0);
- x>>=1;
- }
- reverse(v.begin(),v.end());
- if(ch=='+') insert(v.size());
- else if(ch=='-') del(v.size());
- else search(v.size());
- }
- del_full_trie(root); //killed the trie
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment