c++ - 给定 N 个输入和 p,q 的算法 : find max Xor in array for various interval limis,，其中 0<=p<=i<=q<=N

Question

问题描述如下:

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< 2^15). Each of next Q lines describe a query which consists of three integers ai,pi and qi (0<=ai< 2^15, 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.

int xArray[100000];
cin >>t; 
for(int j =0;j<t;j++)   
{        
    cin>> n >>q;
    
    //int* xArray = (int*)malloc(n*sizeof(int));
    int i,a,pi,qi;        
    
    for(i=0;i<n;i++)
    {
        cin>>xArray[i];                         
    }
    
    for(i=0;i<q;i++)
    {
      cin>>a>>pi>>qi;
        int max =0;
      for(int it=pi-1;it<qi;it++)
      {
          int t =  xArray[it] ^ a;
          if(t>max)               
              max =t;
          
      }   
      cout<<max<<"\n" ;
    } 

除了问题文本中所述的假设之外，不得做出其他假设(数字未排序)。代码可以正常运行，但速度不够快；从标准输入读取真的那么慢还是我还缺少其他东西？

Answer 1

异或翻转位。 XOR的最大结果是0b11111111。

为了得到最好的结果

• 如果第 i 位上的“a”为 1，则必须将其与第 i 位 = 0 的 key 进行异或
• 如果第 i 位的“a”为 0，则必须将其与第 i 位 = 1 的 key 进行异或

简单地说，对于位B，你需要!B

另一个明显的事情是高阶位比较低阶位更重要。

即:

• 如果最高位上的“a”有 B，并且您找到了最高位的 key = !B
• 那么所有具有最高位 = !B 的键都比这个键更糟糕

这会将您的数字数量“平均”减少一半。

如何从所有键构建一个巨大的二叉树，并按位(从 MSB 到 LSB)对树中的它们进行排序。然后，从 MSB 到 LSB 逐位切割 A 会告诉您接下来要采用哪个左右分支以获得最佳结果。当然，这会忽略 PI/QI 限制，但肯定会给您带来最佳结果，因为您总是在第 i 个级别上选择最佳可用位。

现在，如果您使用其子元素的低/高索引范围来注释树节点(在构建树时仅执行一次)，那么稍后在针对案例 A-PI-QI 进行查询时，您可以使用它来过滤掉不在索引范围内的分支。

关键是，如果您对树级别进行排序，例如 MSB->LSB 位顺序，那么在“上节点”执行的决策可以保证您当前处于最佳可能的分支，并且它甚至可以保持如果所有的子分支都是最差的:

处于第 3 级，结果

0b111?????

然后可以扩展为

0b11100000
0b11100001
0b11100010

等等，但即使?????扩展性较差，总体结果还是大于

0b11011111

如果您在第 3 级选择了另一个分支，这将是最好的结果。

我完全不知道准备树需要多长时间，但是查询它的 32 位 A-PI-QI 似乎需要 32 次 N 比较和跳转，肯定比随机迭代 0- 更快100000 次和异或/最大。由于您有多达 50000 个查询，因此构建这样的树实际上是一项不错的投资，因为每个键集都会构建一次这样的树。

现在，最好的部分是您实际上不需要整棵树。您可以仅从前两位、四位或八位构建此类，并使用节点的索引范围将 xor-max 循环限制为更小的部分。在最坏的情况下，你最终会得到与 PiQi 相同的范围。充其量，它会减少到一个元素。

但是，看看最大 N 个键，我认为整个树实际上可能适合内存池，并且您可以在没有任何 xor-maxing 循环的情况下逃脱。