补题地址：https://nanti.jisuanke.com/t/A1607

题目：

 

Consider an array A with n elements . Each of its element is A[i](1≤i≤n). Then gives two integers Q, K, and Q queries follow . Each query , give you L, R, you can get Z by the following rules.

To get Z , at first you need to choose some elements from A[L] to A[R] ,we call them A[i1],A[i2]…A[it] , Then you can get number Z=K or (A[i1] xor A[i2] … xor A[it​]) .

Please calculate the maximum ZZ for each query .

Input

Several test cases .

First line an integer T (1≤T≤10) . Indicates the number of test cases.Then T test cases follows . Each test case begins with three integer N, Q,K (1≤N≤10000, 1≤Q≤100000, 0≤K≤100000). The next line has N integers indicate A[1] to A[N] (0≤A[i]≤108). Then Q lines , each line two integer L，R (1≤L≤R≤N).

Output

For each query , print the answer in a single line.

样例输入 

1
5 3 0
1 2 3 4 5
1 3
2 4
3 5

样例输出 

3
7
7

解题思路：

求区间异或值or已知数k的最大值，区间问题，多次查询，要用到线段树，线段树的叶子节点是单个的线性基，非叶子都是合并后的线性基。

线性基的合并可以参考这道例题。

本题很关键的一个点：因为要求或之后的结果最大，k已知，那么k中为1的位或之后还是1，所以k中为0的那些位需要用区间异或值来弥补，这就是说，k中为0的那些位，在区间异或值中尽量为1，且求最大异或值时只考虑区间的数m 在k中为0的那些位。此时，我们不关心区间异或值是否取最大，或者取多少，只要最终的整个结果最大即可。

对k各位取反，在让区间中的值都和取反后的k做与运算，这样以后，原k中为1的那些位 在区间中的数上 都是0 （因为k中为1的位取反后是0，0和任何数与都是0），而区间的数中为1的位说明 原k中那些位为0，原数中那些位为1。所以最终答案就变成了求新区间的数的最大异或值（让原k中为0的那些位所表示的数最大），再与原k做或运算（原k中为1的那些位在最大异或值中都是0），举个例子试试吧。

ac代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=10005;
const int max_base=30;
typedef long long ll;
int a[maxn],xian[4*maxn][max_base+3],ans[max_base+3];
int n,q,k,t,L,R;
void update(int id)
{
    int x=id<<1,y=id<<1|1;
    memcpy(xian[id],xian[x],sizeof(xian[x]));//id的线性基初始化左子树的线性基
    for(int k=max_base;k>=0;k--)
    {
        int tmp=xian[y][k];
        for(int j=max_base;j>=0 && tmp;j--)
        {
            if(tmp>>j&1)
            {
                if(xian[id][j])
                    tmp^=xian[id][j];
                else
                {
                    xian[id][j]=tmp;
                    break;
                }
            }
        }
    }
}
void build(int l,int r,int id)
{
    if(l==r)
    {
        for(int i=max_base;i>=0;i--)
            if(a[l]>>i&1)
            {
                if(xian[id][i])
                    a[l]^=xian[id][i];
                else
                {
                    xian[id][i]=a[l];
                    break;
                }
            }
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
    update(id);
}
void query(int l,int r,int x,int y,int id)//要查的区间为（x,y）
{
    if(x<=l && r<=y)//如果区间不能直接查到的话，线性基合并,合并的结果存入ans【】中
    {
        for(int k=max_base;k>=0;k--)
        {
            int tmp=xian[id][k];
            for(int j=max_base;j>=0 && tmp;j--)
            {
                if(tmp>>j&1)
                {
                    if(ans[j])
                        tmp^=ans[j];
                    else
                    {
                        ans[j]=tmp;
                        break;
                    }
                }
            }
        }
        return ;//记得写！
    }
    int mid=(l+r)>>1;
    if(x<=mid) query(l,mid,x,y,id<<1);
    if(y>=mid+1) query(mid+1,r,x,y,id<<1|1);
}
int main() {
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {

        memset(xian,0,sizeof(xian));
        scanf("%d %d %d",&n,&q,&k);
        k=~k;
        for(int i=1;i<=n;i++)
        {
            scanf("%d", &a[i]);
            a[i]&=k;
        }
        k=~k;
        build(1,n,1);
        while(q--)
        {
            scanf("%d %d",&L,&R);
            memset(ans,0,sizeof(ans));
            query(1,n,L,R,1);
            int res=0;
            for(int i=max_base;i>=0;i--)
                res=max(res,res^ans[i]);
            printf("%d\n",res|k);
        }
    }
    return 0;
}