应用

我们知道，运用线性基中的一些元素进行亦或，可以得到原序列中的任意元素（当然针对性质3，序列中的0需要单独讨论），利用这样的性质，我们就可以解决很多OI中的关于元素亦或的问题了！(*^▽^*)

• 线性基的构造

　　我们用a数组来存储原序列中的元素，用b数组来存储线性基中的元素。我们可以尝试将a中的元素插入线性基。

 1 for(int i=1;i<=n;i++)
 2     {
 3         ll x=a[i];
 4         for(int j=50;j>=0;j--)
 5         if(x&(1ll<<j)) //注意当j超过31时要用1ll，不然会爆掉（QAQ我就在这调了好久）
 6         {
 7             if(!b[j]) 
 8             {
 9                 b[j]=x;
10                 break;//插入成功后记得退出哦！
11             }
12             else x^=b[j];
13         }
14     }

对于x而言，每次能进行插入的实质上是它的最高位（二进制下），如果插入成功就可以直接退出，否则与b数组该位的元素进行亦或（通过手玩推理可以发现这样插入可以保证能亦或出序列中的原元素）。

• 查询最大值

对于查询序列中能亦或出的最大值，我们可以采用贪心的思想，把b数组从大往小枚举，如果能够使当前答案变大，就亦或上该b数组中的元素。

1 ll qmax()
2 {
3     ll ans=0;
4     for(int i=50;i>=0;i--) if((ans^b[i])>ans) ans^=b[i];
5     return ans;
6 } 

证明：对于每一个非0的bi，其二进制上的i+1位都为1，如果当前答案亦或上改元素大于原答案，证明原答案第i+1位上为0，因为是从大往小枚举，因此亦或只会对答案i+1位以后产生影响，且就算后i位全从1变成0也比第i+1位从0变成1的贡献小，故该贪心是正确的。

• 查询最小值

　　考虑b数组各元素最高位不同，故每次由小的b亦或大的b都会使小的b变大，且b的值随i值的增大而增大（非零状况下），所以可以分两类考虑：

　　①当原序列能亦或出0时，直接输出0；

　　②如果原序列不能亦或出0，那么将b数组由i值从小到大枚举，第一个非0的b值即为答案。

1 ll qmin()
2 {
3     if(fl) return 0;//fl==1指能亦或出0
4     for(int i=0;i<=50;i++) if(b[i]) return b[i];
5 }

　　（未完待续...）