我想出了这个问题。

有一个加密算法，使用逐位XOR运算广泛。这种加密算法使用非负整数x 1 ，X 2 的顺序，... X N 的关键。为了有效地实现这种算法，Xorq需要找到最大值（一个异或x Ĵ），用于给定的一个整数，p和q，使得P＆其中; = J＆其中; = Q。帮助Xorq来实现此功能。

输入

输入的第一行包含一个整数T（1＆LT; = T＆LT; = 6）。 T检验案例可循。

首先每个测试用例行包含两个整数N及Q由单个空格分隔（1＆LT; = N＆LT; = 100,000; 1＆LT; = Q＆LT; = 50,000）。下一行包含N个整数x 1 ，X 2 ，... X N 由一个空格（0℃分离; = X Ĵ＆LT; 215）。每个接下来的Q行描述了由三个整数的我的查询，P 我和Q 我（0℃= A 我＆LT; 215，1＆LT; = P 我＆LT; = Q 我＆LT; = N）

输出

对于每个查询，打印的最大值（我异或x Ĵ），使得P 我＆LT; = J＆LT; = Q 我在一行。

采样输入

  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
 

示例输出

  13
1016
41
191
191
15
107
47
 

说明

 首先查询（10 6 10）：5233 XOR 10 = 12，
    x7的异或10 = 13，x8的异或10 = 2，异或X9 10 = 3，X10的异或10 = 0，
    因此，对于这个查询的答案是13。
第二个查询（1023 7 7）：X7 XOR 1023 = 1016，
    因此，回答这个查询是1016。
第三个查询（33 5 8）：X5 XOR 33 = 36，5233 XOR 33 = 39，
    X7 XOR 33 = 38，X8 XOR 33 = 41，因此该查询的答案是41。
第四查询（182 5 10）：X5 XOR 182 = 179，
    5233 XOR 182 = 176，X7 XOR 182 = 177，X8 XOR 182 = 190，
    X9 XOR 182 = 191，X10 XOR 182 = 188，
    因此，回答这个查询191。
 

我首先做的数字长度（二进制）尝试这个 在给定的范围内相等，然后比较一位由 与特定XJ位values​​.But是时候超越。 最大时间限制在java中是5秒。

我没有通过你的code详细了，但你似乎有环比R = p的范围 - 1;为r q - 1; - [R ++和这将是很好不会有这样做。

由于AI，我们要找出在给定的范围内尽可能多的最高位AI的逆尽可能喜的值。一切都是从0到2 ^ 15，所以不会有太多的比特担心。对于n = 1〜15可以根据其N最高位划分十一起来，所以把它分为2，4，8，16 .. 32768部。对于每一个部分保持一个列表在发现每个可能值的位置排序顺序，所以对于最高位，你将有两个列表，给处的位置的位模式为0 ......... .....和一个定案的位模式为1 ............对于每个三联，您可以使用二进制印章上的一个特定部分，以寻找是否有内任何位置的位置你的范围时，前n位中有你正在寻找的位模式。如果他们这样做，挺好的。如果没有，你将不得不接受的是，异或位置之一为0，稍微修改你找多一个最高位设置模式。

的设置成本是15线越过喜，这可能是低于它把你读它的时候。对于每一行，你可以做15二进制印章看到这顶n位值喜的比赛，和修改顶位你看看，如果你不能匹配特定位的模式。

我想，如果你通过问题codeA独立的子程序分开的问题，code中的I / O程序会更清晰。这也将使其更容易的问题，code一个版本比较与另一个，看看这是更快，如果他们都得到了相同的答案。

I came up with this question.

There is 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 <= xj < 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.

I tried this by first making the numbers length(in binary) in the given range equal and then comparing 'a' bit by bit with the particular xj values.But it is time exceeding. Maximum time limit in java is 5sec.

I haven't gone through your code in detail, but you seem to have loops over the range of r = p - 1; r < q - 1; r++, and it would be nice not to have to do this.

Given ai, we want to find a value of xi in the given range with as many of its top bits the inverse of ai as possible. Everything is between 0 and 2^15, so there aren't many bits to worry about. For n = 1 to 15 you could divide the xi up according to its n highest bits, so dividing it into 2, 4, 8, 16.. 32768 portions. For each portion keep a list in sorted order of the positions where each possible value is found, so for the top bit you will have two lists, one giving the positions at which the bit pattern is 0.............. and one giving the position at which the bit pattern is 1............ For each triple, you can use binary chop on a particular portion to find if there are any positions within your range at which the top n bits have the bit pattern you are looking for. If they do, fine. If not you will have to accept that one of the xor positions is 0 and slightly modify the pattern you look for with one more top bit set.

The setup cost is 15 linear passes over the xi, which is probably less time than it takes you to read it in. For each line you could do 15 binary chops to see which values of xi match in the top n bits, and modify the pattern of top bits you look for if you can't match a particular bit.

I think your program would be clearer if you separated the I/O from the problem code by making the problem code a separate subroutine. This would also make it easier to compare one version of the problem code with another, to see which is faster and if they both get the same answer.