try_n_catch's blog

By try_n_catch, history, 6 years ago, In English

Recently I was trying the question Maximum Xor Query of codechef. I decided to go for the editorial there I found to build a segment tree with each node being a trie. I am not able to understand the following piece of code that how they are finding maximum xor. Can anyone help me out??

int solve(vi &vec, int v) {

/*cout<<"VEC : ";
for(int i = 0; i < vec.size(); i++)
{
    cout<<vec[i]<<' ';
}
cout<<'\n';*/
int l = 0; int r = vec.size() - 1;
int cur = 0;
int ans = 0;
//cout<<l<<" "<<r<<endl;
for(int i = 24 - 1; i >= 0; i--)
{
    if(v&(1<<i))
    {
       int x = lower_bound(vec.begin()+l, vec.begin()+r+1, cur+(1<<i)) - vec.begin();
       cout<<1<<" "<<x<<endl;
       if(l<=x-1)
       {
         r = min(r, x-1);
         ans+=(1<<i);
       }
       else
       {
         cur+=(1<<i);
       }
    }
    else
    {
       int x = lower_bound(vec.begin()+l, vec.begin()+r+1, cur+(1<<i)) - vec.begin();
    // cout<<0<<" "<<x<<" "<<i<<endl;
       if(r>=x)
       {
         l = max(x,l);
         ans+=(1<<i);    
         cur+=(1<<i);
       }
    }
}
return ans;

}

  • Vote: I like it
  • -11
  • Vote: I do not like it