HackerEarth Minimum XOR problem solution

In this HackerEarth Minimum XOR problem solution You are given Q queries of two types:

1. X: Append value X into an array.
2. X K: You are required to print the Kth minimum XOR of X with the current array.

You have to make a new array whose ith element is current_array[i]^x. Then sort it and print the Kth element.

HackerEarth Minimum XOR problem solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define ALL(x) x.begin(),x.end()
#define vec vector<int>
#define LG 63
#define int ll

typedef struct data
{
      data* bit[2];
      int below = 0;
}trie;
 
trie* head;
 
void insert(int x)
{
      trie* cur = head;
      int y = x;
      for(int i=LG ;i>=0 ;i--)
      {
            ll t= (1ll << i );
            int b = (x>>i) & 1;
            cur -> below++  ;
            if(!cur -> bit[b])
                  cur -> bit[b] = new trie();
            cur = cur -> bit[b];
      }
      cur -> below++;
}
 
int query(int y,int k)
{
      ll ans = 0;
      trie* curr = head;
 
      for(int i=LG;i>=0;i--)
      {
            ll t = ( 1ll << i );
            int b = ( y >> i ) & 1;

            ll ava=0;

            if( curr -> bit[b] )
                  ava = curr -> bit[b] -> below;

            if( ava >= k )
            {
                  curr = curr -> bit[b];
            }
            else
            {
                  ans += t;
                  k -= ava; 
                  if( !curr -> bit[!b] )
                        curr -> bit[!b] = new trie();
                  curr = curr -> bit[!b];
            }
      }
      return ans;
}
 
int32_t main()
{

      head=new trie();

      ll q;
      cin >> q;

      while(q--)
      {
            ll t;
            cin>>t;

            if(t==1)
            {
                  ll x;
                  cin >> x;
                  insert(x);
            }
            else
            {
                  ll x,k;
                  cin >> x >> k;
                  cout<<query(x,k)<<"\n";
            }
      }
}