<分区>
引用这里的问题挑战: Link
#include <iostream>
using namespace std;
int main() {
int T,*x,i,j,k,a,res,pres;
long Q,N,p,q;
cin>>T;
for(k=0;k<T;k++)
{
cin>>N>>Q;
x=new int[N];
for(i=0;i<N;i++)
{
cin>>x[i];
}
for(i=0;i<Q;i++)
{
pres=-999;
cin>>a>>p>>q;
for(j=p-1;j<q;j++)
{
res=a xor x[j];
if(pres<res)
{
pres=res;
}
}
cout<<pres<<endl;
}
delete [] x;
}
return 0;
}
我在更大的问题 (N=100000)(N、Q、T 最大化)上遇到了超出时间限制(暗示问题可以优化)。我认为我需要使用某种预处理来优化算法。我的解决方案是整个问题的 O(NQT)。该问题将需要针对查询中给定的限制评估所有可能的 XOR。因此，问题需要进行 (q-p)[最多 N] 次查询。我想不出避免这种情况的方法。命中或方向将不胜感激。我正在考虑以某种方式实现一个堆，以便它从堆中扣除查询 a 并创建一个最大堆以查看最大差异和 den xors。但这也需要 O(NQT)