菜炸了！QAQ，还得继续努力啊！
原文：https://blog.csdn.net/baodream/article/details/83211138
题意：t组数据，然后输入n，k，q，接着给出一个1个长度为n的数组,q个询问，对于每个询问，询问在下标为[l,r]的数中，选取一部分数，使得其异或值再OR上k后最大，输出这个最大值。
思路：根据题意，选取一部分值得到异或最大值，可以想到线性基，但是最后要OR上k，所以要消除k对其影响，我们就把每个数转化成二进制，然后将k为1的位置对于每个数其位置就变为0，这样就可以消除其k的影响了，最后在OR上k变回来，即为正确答案。比如数a[i]=6(110) ,k = 4(100),则a[i]应该变为(010)=2这样来消除k的影响。由于多次区间询问，所以用线段树维护一下即可。
#include<bits/stdc++.h> #define debug(x) cout<<'x'<<' '<<x<<endl; typedef long long ll; const ll INF=1e15; const int maxn = 10467398; const int mod = 1e9+7; using namespace std; typedef long long ll; //线性基 struct L_B{ ll d[63],new_d[63]; //d数组是第一次线性基,new_d是用于求Kth的线性基 int cnt; //记录个数 L_B(){ memset(d,0,sizeof(d)); memset(new_d,0,sizeof(new_d)); cnt=0; } void clear(){ memset(d,0,sizeof(d)); memset(new_d,0,sizeof(new_d)); cnt=0; } bool ins(ll val){ for(int i=62;i>=0;i--){ if(val&(1ll<<i)){ //存在贡献则继续 if(!d[i]){ //线性基不存在,选入线性基中 d[i]=val; break; } val^=d[i]; //否则直接改变其值 } } return val>0; //大于0则是成功加入线性基的向量 } ll query_max(){ ll ans=0; for(int i=62;i>=0;i--) if((ans^d[i])>ans) //能让值变大则选入 ans^=d[i]; return ans; } ll query_min(){ for(int i=0;i<=62;i++) if(d[i]) //最小异或值 return d[i]; return 0; } //以下代码为求第k大异或值，其中cnt用于判断是否可以取到0 // cnt==n（数的个数）则不可以取到0，第k小就是第k小，否则第k小是第k-1小 void rebuild() { for(int i=62;i>=0;i--) for(int j=i-1;j>=0;j--) if (d[i]&(1LL<<j)) d[i]^=d[j]; for (int i=0;i<=62;i++) if (d[i]) new_d[cnt++]=d[i]; } ll kthquery(int k) { ll ans=0; if (k>=(1ll<<cnt)) return -1; for (int i=62;i>=0;i--) if (k&(1ll<<i)) ans^=new_d[i]; return ans; } }; //线性基合并,暴力合并 L_B merge(const L_B &n1,const L_B &n2) { L_B ret=n1; for (int i=62;i>=0;i--) if (n2.d[i]) ret.ins(n2.d[i]); return ret; } ll n,q,k,pd,a[10005]; L_B A; struct node{ int lft,rht; L_B lb; }tree[10005<<2]; void pushUp(int id){ tree[id].lb = merge(tree[id<<1].lb,tree[id<<1|1].lb); } void build(int id,int l,int r){ tree[id].lft=l; tree[id].rht=r; if(l==r){ tree[id].lb.clear(); tree[id].lb.ins((a[l]&pd)); return ; } int mid = (l+r)>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); pushUp(id); } void query(int id,int l,int r){ if(l==tree[id].lft&&r==tree[id].rht) { A = merge(A,tree[id].lb); return ; } int mid = (tree[id].lft+tree[id].rht)>>1; if(r<=mid) { query(id<<1,l,r); } else if(l>mid) { query(id<<1|1,l,r); } else { query(id<<1,l,mid); query(id<<1|1,mid+1,r); } } int main() { std::ios::sync_with_stdio(false); int t; scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&n,&q,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); pd=0; for(int i=0;i<=62;i++){ if(k&(1ll<<i)) ; else pd+=(1ll<<i); } build(1,1,n); int l,r; while(q--){ scanf("%d%d",&l,&r); A.clear(); query(1,l,r); printf("%lld ",A.query_max()|k); } } return 0; }