HackerEarth Shin-Chan Kazama and XOR problem solution

In this HackerEarth Shin-Chan Kazama and XOR problem solution, SHIN-CHAN and KAZAMA grew up to become very good friends. They went to high school together and shared the same bench in the class. In one of the maths classes, while the teacher was teaching the class about the XOR (exclusive OR) operator, the two of them were busy thinking of SHIZUKA (both of them had a big crush on her since childhood days). The teacher saw this and decided to punish them by giving them a punishment for not paying attention in class. As a punishment, he gave them a very difficult assignment in which there were several questions on a sequence of given numbers.

Given an array of integers A [ 1 – N ] , they had to answer a number of queries. Each query had three integers l , r , and X. They had to find a number Z in the array in range A[ l ], A[ l + 1 ], …. A[ r ]. Z for a range and integer X is defined as a number A [ i ] ( l <= i <= r) such that the value of Z, when taken XOR with X, comes out to be lesser than that for any other element in the given range.

As the two of them did not know anything about XOR and were busy planning a surprise for SHIZUKA’s b’day, help them finding the answers of the given queries. The answer to each query is the number Z and the number of times it occurs in the given range.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ft first
#define sd second
#define VI vector<int>
#define VLL vector<long long int>
#define PII pair<int,int>
#define pb push_back
#define rsz(v,n) v.resize(n)

#define scan(x) scanf("%d",&x)
#define scanll(x) scanf("%lld",&x)
#define ll long long int
#define rep(i,x,y) for(i=x;i<y;i++)
#define print(x) printf("%dn",x)
#define printll(x) printf("%lldn",x)
#define all(v) v.begin(),v.end()
#define ms(v) memset(v,0,sizeof(v))
#define FOR(i,a,b)  for(i=a;i<b;i++)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#ifdef ONLINE_JUDGE
 inline void inp1( int &n )
 {
    n=0;
    int ch=getchar_unlocked();int sign=1;
    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

    while(  ch >= '0' && ch <= '9' )
            n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    n=n*sign;
  }
#else
inline void inp1(int &n){
 cin>>n;
}
#endif

struct node{
    int L,R,X,I;
};
vector<node> qty;
int N;
bool compare(const node &a,const node &b)
{
    if(a.L/N==b.L/N)
    {
        return a.R<b.R;
    }
    return a.L<b.L;
}
VI arr;
class Trie{

  private:
   Trie * child[2];
   int count;
   int freqq;
  public:
  Trie(){child[1]=child[0]=NULL;count=0;}

  void initialise(int n,int bit){
    count=0;
    if(bit<0)
    return ;
    bool b=(n&(1<<bit));
    if(child[b]==NULL) child[b]=new Trie();
    child[b]->initialise(n,bit-1);
  }

  void insert(int n,int bit){
    ++count;
    if(bit<0)
    return ;
    bool b=(n&(1<<bit));
    child[b]->insert(n,bit-1);
  }
  void remove(int n,int bit)
  {
    --count;
    if(bit<0) return;
    bool b=(n&(1<<bit));
    child[b]->remove(n,bit-1);
  }

  PII _search(int n,int bit)
  {
      PII temp;
      if(bit<0){temp.ft=0;temp.sd=count; return temp;}
      bool b=(n&(1<<bit));
      if(child[b]!=NULL&&child[b]->count>0)
      {
        temp=child[b]->_search(n,bit-1);
        temp.ft+=(b*(1<<bit));
      }
      else
      {
        temp=child[1-b]->_search(n,bit-1);
        temp.ft+=((1-b)*(1<<bit));
      }
      return temp;
  }
  void print_T()
  {

     if(child[0]!=NULL&&child[0]->count>0)
      {
       print(0);
       child[0]->print_T();
      }
      else if(child[1]!=NULL&&child[1]->count>0){
       print(1);
       child[1]->print_T();
      }

  }

}*root;
bool cmp(const pair<int,PII > &a,const pair<int,PII > &b){ return a.ft<b.ft;}
vector<pair<int,PII > > ans;
int main()
{

    int t;
    t=1;
    //inp(t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        //inp(n);
        arr.resize(n);
        for(int i=0;i<n;i++) scanf("%d",&arr[i]);
        root=new Trie();

        for(int i=0;i<n;i++) root->initialise(arr[i],30);

        N=(int)sqrt(n);
        int Q;
        scanf("%d",&Q);

        qty.resize(Q);
        ans.resize(Q);
        for(int i=0;i<Q;i++)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            l--;
            r--;
            qty[i].L=l;
            qty[i].R=r;
            qty[i].X=x;
            qty[i].I=i;
        }
        sort(all(qty),compare); // compare function using sqrt decomposition
        int left=0,right=-1;
        for(int i=0;i<Q;i++)
        {
            while(right<qty[i].R)
            {
             right++;
             root->insert(arr[right],30);
            }

            while(qty[i].R<right)
            {
                root->remove(arr[right],30);
                right--;
            }

            while(qty[i].L<left)
            {
                left--;
                root->insert(arr[left],30);
            }
            while(left<qty[i].L)
            {
             root->remove(arr[left],30);
             left++;
            }
            ans[i].ft=qty[i].I;
            ans[i].sd=root->_search(qty[i].X,30);
        }

        sort(all(ans));
        for(int i=0;i<Q;i++) printf("%d %dn",ans[i].sd.ft,ans[i].sd.sd);
        arr.clear();
        qty.clear();
    }
    return 0;
}