gistfile1.cpp

#include<iostream>
using namespace std;
#include<math.h>
#include<string.h>

class SegmentTree
{
     int *A,size;
     public:
     SegmentTree(int N)
     {
          int x = (int)(ceil(log2(N)))+1;
          size = 2*(int)pow(2,x);
          A = new int[size];
          memset(A,-1,sizeof(A));
     }
     void initialize(int node, int start,
                         int end, int *array,int a)
     {

          if (start==end)
             A[node] = start;
          else
          {
              int mid = (start+end)/2;
              initialize(2*node,start,mid,array,a);
              initialize(2*node+1,mid+1,end,array,a);
              if ((array[A[2*node]]^a)>(array[A[2*node+1]]^a))
                 A[node] = A[2 * node];
              else
                  A[node] = A[2 * node + 1];
          }
     }
     int query(int node, int start,
                   int end, int i, int j, int *array,int a)
     {
         int id1,id2;
         if (i>end || j<start)
            return -1;

         if (start>=i && end<=j)
            return A[node];

         int mid = (start+end)/2;
         id1 = query(2*node,start,mid,i,j,array,a);
         id2 = query(2*node+1,mid+1,end,i,j,array,a);

         if (id1==-1)
            return id2;
         if (id2==-1)
            return id1;

         if ((array[id1]^a)>(array[id2]^a))
            return id1;
         else
             return id2;
     }
};

int main()
{
    
    int T,N,Q;
    int a,p,q;
    int* keys;
    scanf("%d",&T);
    
    for(int a=0;a<T;a++)
    {
             scanf("%d %d",&N,&Q);
             keys = new int[N];
             for(int j=0;j<N;j++)
             {
                     int keytemp = 0;
                     scanf("%d",&keytemp);
                     keys[j] = keytemp;
             }      
             
             for(int z = 0; z < Q; z++){
                     
                             scanf("%d %d %d",&a,&p,&q);
                             SegmentTree s(N);
                             s.initialize(1,0,N-1,keys,a);
                             printf("%d\n",(keys[s.query(1,0,N-1,p-1,q-1,keys,a)]^a));
                     }
                     
    }
    
    system("PAUSE");
}

XOR key (50 Points)

Xorq has invented an encryption algorithm which uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers x1, x2, ... xn as key. To implement this algorithm efficiently, Xorq needs to find maximum value for (a xor xj) for given integers a,p and q such that p<=j<=q. Help Xorq to implement this function.

Input
First line of input contains a single integer T (1<=T<=6). T test cases follow.

First line of each test case contains two integers N and Q separated by a single space (1<= N<=100,000; 1<=Q<= 50,000). Next line contains N integers x1, x2, ... xn separated by a single space (0<=xi< 215). Each of next Q lines describe a query which consists of three integers ai,pi and qi (0<=ai< 215, 1<=pi<=qi<= N).

Output
For each query, print the maximum value for (ai xor xj) such that pi<=j<=qi in a single line.

Sample Input
1
15 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 6 10
1023 7 7
33 5 8
182 5 10
181 1 13
5 10 15
99 8 9
33 10 14

Sample Output
13
1016
41
191
191
15
107
47

Explanation
First Query (10 6 10): x6 xor 10 = 12, x7 xor 10 = 13, x8 xor 10 = 2, x9 xor 10 = 3, x10 xor 10 = 0, therefore answer for this query is 13.
Second Query (1023 7 7): x7 xor 1023 = 1016, therefore answer for this query is 1016.
Third Query (33 5 8): x5 xor 33 = 36, x6 xor 33 = 39, x7 xor 33 = 38, x8 xor 33 = 41, therefore answer for this query is 41.
Fourth Query (182 5 10): x5 xor 182 = 179, x6 xor 182 = 176, x7 xor 182 = 177, x8 xor 182 = 190, x9 xor 182 = 191, x10 xor 182 = 188, therefore answer for this query is 191.

this solution will get TLE as building the tree costs N Lg(N) .. so this solutions costs Q N lg(N) which is too big..