题意 :给出一个包含n个元素的数组A以及一个k，接下来进行q次询问，每次询问给出 l 和 r ，
要你求出从A[l] , A[l+1] , A[l + 2],...,A[r]中任选出若干个数异或起来的值val，使得 k | val 最大，输出这个最大值。
思路 ：既然是要使得k | val得到的值最大，那么val必然是k这个数上二进制位为0的位置为1的数，同时1的位数要尽可能的多。
这样我们就可以先对k取反，求出k二进制位为0的位数变成1的数p，再用A[i]与上p，将这些数放入线性基中。
由于每次都是区间查询，我们就可以利用线段树的思想，建立一棵结点为线性基的线段树，
每次区间查询的时候就查询出这几个区间合并后的线性基，再用线性基的性质查询最大值即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 12345
ll t,n,k,q,l,r,a[maxn],ans;
struct node
{
ll p[66];
void init()
{
memset(p,0,sizeof(p));
}
node()
{
memset(p,0,sizeof(p));
}
void add(ll x)
{
for(int i=60; i>=0; i--)
{
if(!(x&(1<<i)))continue;
if(!p[i])
{
p[i]=x;
break;
}
else x^=p[i];
}
}
node operator+(const node &b)const
{
node ret=b;
for(int i=60; i>=0; i--)
if(p[i])ret.add(p[i]);
return ret;
}
ll rp()
{
ll re=0;
for(int i=60; i>=0; i--)
if((re^p[i])>re)re^=p[i];
return re;
}
} tree[maxn*4];
void up(int root)
{
tree[root]=tree[root*2]+tree[root*2+1];
}
void bulid(int root,int l,int r)
{
tree[root].init();
if(l==r)
{
tree[root].add(a[l]);
return ;
}
int mid=(l+r)/2;
bulid(root*2,l,mid);
bulid(root*2+1,mid+1,r);
up(root);
}
node query(int root,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
return tree[root];
int mid=(l+r)/2;
if(L>mid)return query(root*2+1,mid+1,r,L,R);
else if(R<=mid)return query(root*2,l,mid,L,R);
else return query(root*2,l,mid,L,R)+query(root*2+1,mid+1,r,L,R);
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&q,&k);
k=~k;
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
a[i]=(a[i]&k);
}
k=~k;
bulid(1,1,n);
while(q--)
{
ans=k;
scanf("%lld%lld",&l,&r);
node tp=query(1,1,n,l,r);
ans=(ans|tp.rp());
printf("%lld\n",ans);
}
}
return 0;
}