前言
线性基是一种处理异或问题的利器，拥有优秀的时间复杂度
基本性质
概念
定义：给定数集 \(S\) ，以异或运算张成的数集与 \(S\) 相同的极大线性无关集，称为原数集的一个线性基。
通俗地说，线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原序列中的任何一个数。
基本性质
1、线性基中的数最高位互不相同
2、线性基中的数互相异或可以得到原序列中的任何一个数
3、线性基中的数没法异或出0
4、线性基是满足性质2的情况下的最小集合，且大小唯一。
5、线性基子集的异或和具有唯一性
证明咕咕咕
基本操作
插入
设数组 \(p\) 表示序列 \({a_n}\) 的线性基，待插入数为 \(x\)，下标从 \(0\) 开始。
我们聚焦性质1，可以发现，如果想让线性基中的数最高位互不相同，就要用贪心的思想，在能匹配进去的时候匹配进去。所以我们将 \(x\) 转为二进制，从它的高位开始，如果当前位为 \(1\)，并且线性基 \(p\) 的第 \(i\) 位上没有数，那就赋成当前值 \(x\)。
如果发现这时候第 \(i\) 位上有数，那么就让 \(x\) 异或上 \(p_i\) 后继续按最高位匹配。
为什么这样做是可行的？
不妨假设 \(x\) 在匹配时经过了 \(p\) 中的 \(q\) 个位置，分别为 \(b_1\) 至 \(b_q\) 那么我们将这些位置上的 \(p\) 异或起来，就能得到原来的 \(x\) ，因为我们在匹配过程中，相当于每次失配的时候都把当前的 \(x\) 拆分成了 \(p_i\) 和 \(p_i \; xor \;x\) ，之后我们再用后半部分去匹配，因此我们把所有经过的位置的线性基中的数给异或起来，我们就得到了原数。
bool insert(ll x){
for(int i=60;i>=0;i--){
if(x>>i&1){
if(!p[i]){ p[i]=x;return true;}
x^=p[i];
}
}
return false;//判断能否插入成功
}
查最大值
因为线性基中每个数的最高位互不相同，而且异或运算里每一位都是独立的，所以我们要想求异或后的全局最大值，我们只需要从高位向低位依次尝试加入后能否是当前答案变大即可。
ll found_max(){
ll ans=0;
for(int i=60;i>=0;i--) ans=max(ans,ans^p[i]);
return ans;
}