参考资料：
[1]:在线线性基
[2]:离线线性基
[3]:离线线性基
•题意
给你 n 个数，m 次询问；
每次询问给定一个区间 $l,r$，求 $a_{l \cdots r}$ 异或的最大值；
•线段树+线性基
参考了一下资料[1]，学会了如何将线性基和线段树结合；
虽然在此题中会 TLE，但是却学到了不少东西；
首先，在建树的时候，将叶节点上的值插入到线性基中；
在回溯的时候，通过 Merge 操作，将 pos 的儿子节点的线性基合并到 pos 的线性基上；
类似于常规线段树中的 pushUp 操作；
此算法可以用来做这道题：洛谷P4839
•Code(线段树TLE版本)
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ls(x) (x<<1) 4 #define rs(x) (x<<1|1) 5 const int maxn=5e5+50; 6 7 int n,q; 8 int a[maxn]; 9 struct Seg 10 { 11 int l,r; 12 int a[25]; 13 int mid(){return l+((r-l)>>1);} 14 void Insert(int x) 15 { 16 for(int i=20;i >= 0;--i) 17 { 18 if(x&(1<<i)) 19 { 20 if(!a[i]) 21 { 22 a[i]=x; 23 return ; 24 } 25 x ^= a[i]; 26 } 27 } 28 } 29 int Max() 30 { 31 int ans=0; 32 for(int i=20;i >= 0;--i) 33 ans=max(ans,ans^a[i]); 34 return ans; 35 } 36 }seg[maxn<<2]; 37 38 Seg Marge(Seg a,Seg b) 39 { 40 Seg tmp=b; 41 for(int i=0;i <= 20;++i) 42 if(a.a[i]) 43 tmp.Insert(a.a[i]); 44 return tmp; 45 } 46 void buildSeg(int l,int r,int pos) 47 { 48 seg[pos].l=l; 49 seg[pos].r=r; 50 51 if(l == r) 52 { 53 seg[pos].Insert(a[l]); 54 return ; 55 } 56 57 int mid=l+((r-l)>>1); 58 buildSeg(l,mid,ls(pos)); 59 buildSeg(mid+1,r,rs(pos)); 60 61 seg[pos]=Marge(seg[ls(pos)],seg[rs(pos)]); 62 seg[pos].l=l;///此处要注意，因为Marge返回的结果未给l,r赋值 63 seg[pos].r=r; 64 } 65 Seg Query(int l,int r,int pos) 66 { 67 if(seg[pos].l == l && seg[pos].r == r) 68 return seg[pos]; 69 70 int mid=seg[pos].mid(); 71 72 if(r <= mid) 73 return Query(l,r,ls(pos)); 74 else if(l > mid) 75 return Query(l,r,rs(pos)); 76 else 77 return Marge(Query(l,mid,ls(pos)),Query(mid+1,r,rs(pos))); 78 } 79 void Solve() 80 { 81 for(int i=1;i <= q;++i) 82 { 83 int l,r; 84 scanf("%d%d",&l,&r); 85 86 Seg ans=Query(l,r,1); 87 88 printf("%d\n",ans.Max()); 89 } 90 } 91 int main() 92 { 93 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 94 scanf("%d",&n); 95 for(int i=1;i <= n;++i) 96 scanf("%d",a+i); 97 buildSeg(1,n,1); 98 99 scanf("%d",&q); 100 Solve(); 101 102 return 0; 103 }View Code
•离线线性基
学会了和线段树结合后，看了看正解 线性基+贪心，果然，看不懂；
放弃了这个解法，找了几篇离线线性基的做法（资料[2],[3]）；
大致做法是，将所有询问收集起来，并按照 r 升序排列；
边插入 ai 边判断当前的 i 是否为当前询问的右端点；
插入的时候，记录两个数值 base[ i ] , p[ i ]，表示第 p[ i ] 个数 $a_{p_i}$ 在通过 Insert() 操作时，插入的时候插到了 base[ i ] 中；
每次插入第 i 个数 ai 时，优先让高位的 1 用当前的位置来表示，这样可以保证高位的 1 对应的 base 值可以对最大值有贡献；
•Code(离线)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5e5+50; 4 5 int n,m; 6 int a[maxn]; 7 struct Query 8 { 9 int l,r; 10 int pos; 11 bool operator < (const Query &obj) const 12 { 13 return r < obj.r; 14 } 15 }q[maxn]; 16 int base[30]; 17 int p[30]; 18 int ans[maxn]; 19 20 void Insert(int pos,int x) 21 { 22 for(int i=20;i >= 0;--i) 23 { 24 if(x&(1<<i)) 25 { 26 if(!base[i]) 27 { 28 base[i]=x; 29 p[i]=pos; 30 return ; 31 } 32 else if(pos > p[i])///第i位的base[i]优先让p大的表示 33 { 34 swap(base[i],x); 35 swap(p[i],pos); 36 } 37 x ^= base[i]; 38 } 39 } 40 } 41 int Max(int k) 42 { 43 int l=q[k].l; 44 int r=q[k].r; 45 46 int ans=0; 47 ///查询时，保证p大的高位base优先考虑 48 for(int i=20;i >= 0;--i) 49 if(p[i] >= l && p[i] <= r) 50 ans=max(ans,ans^base[i]); 51 return ans; 52 } 53 void Solve() 54 { 55 sort(q+1,q+m+1); 56 57 int k=1; 58 for(int i=1;i <= n;++i) 59 { 60 Insert(i,a[i]); 61 62 while(i == q[k].r) 63 { 64 65 ans[q[k].pos]=Max(k); 66 k++; 67 } 68 } 69 70 for(int i=1;i <= m;++i) 71 printf("%d\n",ans[i]); 72 73 return ; 74 } 75 int main() 76 { 77 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 78 scanf("%d",&n); 79 for(int i=1;i <= n;++i) 80 scanf("%d",a+i); 81 82 scanf("%d",&m); 83 for(int i=1;i <= m;++i) 84 { 85 scanf("%d%d",&q[i].l,&q[i].r); 86 q[i].pos=i; 87 } 88 89 Solve(); 90 91 return 0; 92 }View Code
•在线线性基
学会了离线的，再看资料[1]的正解代码时，理解起来容易了不少；
•Code(在线)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5e5+50; 4 5 int n,q; 6 int a[maxn]; 7 int base[maxn][30]; 8 int p[maxn][30]; 9 10 void Insert(int pos,int x,int k) 11 { 12 for(int i=20;i >= 0;--i) 13 { 14 if(x&(1<<i)) 15 { 16 if(!base[k][i]) 17 { 18 base[k][i]=x; 19 p[k][i]=pos; 20 } 21 else if(pos > p[k][i]) 22 { 23 swap(pos,p[k][i]); 24 swap(x,base[k][i]); 25 } 26 x ^= base[k][i]; 27 } 28 } 29 } 30 int Max(int l,int r) 31 { 32 int ans=0; 33 for(int i=20;i >= 0;--i) 34 if(p[r][i] >= l) 35 ans=max(ans,ans^base[r][i]); 36 return ans; 37 } 38 void Solve() 39 { 40 for(int i=1;i <= n;++i) 41 { 42 memcpy(base[i],base[i-1],sizeof(base[i-1])); 43 memcpy(p[i],p[i-1],sizeof(p[i-1])); 44 45 Insert(i,a[i],i); 46 } 47 48 while(q--) 49 { 50 int l,r; 51 scanf("%d%d",&l,&r); 52 53 printf("%d\n",Max(l,r)); 54 } 55 } 56 int main() 57 { 58 scanf("%d",&n); 59 for(int i=1;i <= n;++i) 60 scanf("%d",a+i); 61 scanf("%d",&q); 62 63 Solve(); 64 65 return 0; 66 }View Code