【題目描述】
UVALive - 8512XOR
【題目分析】
這種區間+線性基的問題我們可以考慮用線段樹維護，線性基的合并的話就直接暴力合并
找到所在區間的線性基后再查找最大的數，我看網上的博客要說消除k的影響什么的，我覺得沒有什么必要，直接將初值設置為k，然后從高位向低位找，如果異或了后值會變大就異或，覺得沒有什么大問題。還有就是線段樹維護的時候函數的返回值最好不要設置成線性基，會RE，具體的為什么我也不清楚。這道題的RE很玄學，我把讀入數據改成longlong就會RE，T和u，v里面都一個不是longlong就不會RE，我提交了20多次才敢確定的確是因為這個原因導致RE，emmm，比較玄學
【AC代碼】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>using namespace std;typedef long long ll;const int MAXN=10005;
int n,m,kk;
int a[MAXN];
struct L_B
{ll b[65],p[65];int cnt,flag;L_B(){memset(p,0,sizeof(p));memset(b,0,sizeof(b));cnt=flag=0;}void clear(){memset(p,0,sizeof(p));memset(b,0,sizeof(b));cnt=flag=0;}inline bool insert(ll x){for(int i=62;i>=0;--i)if(x&(1ll<<i)){if(b[i])x^=b[i];else{b[i]=x;return true;}}flag=1;return false;}ll get_max(){ll ret = 0;for(int i=62;i>=0;--i)if((ret^b[i])>ret)ret^=b[i];return ret;}ll get_max(ll initval){ll ret = initval;for(int i=62;i>=0;--i)if((ret^b[i])>ret)ret^=b[i];return ret;}ll get_min(){if(flag)return 0;for(int i=0;i<=62;++i)if(b[i])return b[i];return 0;}inline void rebuild(){for(int i=1;i<=62;++i)if(b[i])for(int j=0;j<i;++j)if(b[i]&(1ll<<j))b[i]^=b[j];for(int i=0;i<=62;++i)if(b[i])p[cnt++]=b[i];}ll kth(ll k){if(flag)--k;if(k==0)return 0;ll ret = 0;if(k>=(1ll<<cnt))return -1;for(int i=0;i<=cnt-1;++i)if(k&(1ll<<i))ret^=p[i];return ret;}
};
L_B A;
struct node
{L_B lis;
}tree[MAXN<<2];L_B merge(const L_B &n1,const L_B &n2)
{L_B ret = n1;for(int i = 0;i <= 62;++i)if(n2.b[i])ret.insert(n2.b[i]);ret.flag = n1.flag | n1.flag;return ret;
}void build(int k,int l,int r)
{if(l==r){tree[k].lis.insert(a[l]);return;}int mid=(l+r)>>1;build(k<<1,l,mid); build(k<<1|1,mid+1,r);tree[k].lis=merge(tree[k<<1].lis,tree[k<<1|1].lis);
}void query(ll k,ll l,ll r,ll L,ll R)
{if(l>=L && r<=R){A=merge(A,tree[k].lis);return;}int mid=(l+r)>>1;if(L<=mid) query(k<<1,l,mid,L,R);if(R>mid) query(k<<1|1,mid+1,r,L,R);return ;
}int main()
{ll T,u,v;scanf("%lld",&T);while(T--){scanf("%d%d%d",&n,&m,&kk);for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(1,1,n);for(int i=0;i<m;i++){A.clear();scanf("%lld%lld",&u,&v);query(1,1,n,u,v);printf("%lld\n",A.get_max(kk));}}return 0;
}
