前言
首先讲一下线性基是什么东西，线性基是一个集合，你在原集合中找到一个子集，子集中的数xor起来一定能在线性基中找一个对应子集的xor和与其相等。
比如说，{x,y}和{x,x^y} 就满足这么样一个关系。
原理
我们把这个扩展一下，比如说我们现在有一个集合A，我新加进来一个数a，那么a与A中的数xor一下肯定是没有问题的。
性质
定义一个数的M值为他二进制上第一个1出现的位置。
我们每往线性基中插入一个数，我们要让这个数的M值与之前线性基中的每一个数的M值都不同。
插入
那么如何实现呢？1
2
3
4
5
6
7
8
9
10
11void insert(LL c){
for (int i=51;i>=0;i--){
if (c&bit[i]){
if (!xxj[i]){
xxj[i]=c;
break;
}
c=c^xxj[i];
}
}
}
在这里，xxj[i]表示目前线性基中M值为i的这个数是多少。
那么当我们新插入一个数C
我们从大到小枚举C的每一个二进制位，如果当前位置上为1，如果对应的xxj[i]没有数，那么这个数就变成xxj[i]，否则xor上xxj[i]，通过我们前面的原理，这样正确性是对的，而且这样我们再扫后面的位置时，保证出现的1就是第一个出现的
例：
xxj[3]=101
xxj[2]=0
插入110
110—>11
所以插入xxj[2]的时候M值已经为2了（这个应该比较好想）
那么我们就完成了线性基的插入，基于二进制位，所以插入的复杂度是log的，而且通过这种插入方式，我们线性基的大小就是基于二进制的位数了，log个。
合并
合并两个线性基只需要把一个线性基暴力插入另一个即可，复杂度：线性基大小*插入复杂度，log方
删除
这种不加特技的线性基不支持删除操作
取最大值
我们从最高位倒着扫下来，扫到第i位，如果当前的答案ans这一位上为1，那么我们xor上xxj[i]一定只会变小，而且这个影响无法消除，因为xxj[i+1..n]都不可能在那ans第i位上变为1，（根据xxj[i]的性质），同理，如果ans这一位上位0，那么xor上ans[i]一定会让答案变大。
当然如果xxj[i]==0,那就没有影响1
2
3
4
5
6
7LL query_max(){
LL ret=0;
for (int i=51;i>=0;i--){
if ((xxj[i]^ret)>ret) ret=ret^xxj[i];
}
return ret;
}
取xor d的最大值
那么只需要把ret的初值赋为d就行了，原理也和上面的相同
取最小值
只需要找到最小的i，且xxj[i]不等于0就行了
取k小值
乍一看，一般的线性基好像不可做，
问题在哪儿？
1000001
0000001
同时选1和2比只选1要差，所以我们无法做
但是如果线性基长成这样
1000000
0100000
0010000
0001000
0000100
那么就好做了，因为选取1和2一定比只选1要优。
所以我么需要对原来的线性基rebuild一下，使得它变成上面那样的形式，当然
1000010
0100001
0000101
这种形式也是可以的，xxj[最后一位]上没有数，所以同时选2和3也比只选2优，尽管最后一位上的1被消掉了
所以我们要使得若xxj[i]!=0，那么线性基里其他的数第i位上都为0，所以我们只需要拿xxj[i]去xor一下那些数就好了。
rebuild之后的线性基怎么做：把k转成二进制，若k的第i位为1，那么将ans xor 上rebuild后第i大的xxj就行了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void rebuild()
{
for (int i=60;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<=60;i++)
if (d[i])
p[cnt++]=d[i];
}
long long kthquery(long long k)
{
int ret=0;
if (k>=(1LL<<cnt))
return -1;
for (int i=60;i>=0;i--)
if (k&(1LL<<i))
ret^=p[i];
return ret;
}
以上就是我对线性基的一些个人理解，希望能帮助大家学习，谢谢
同时在此感谢Yveh的博客给了很大帮助。
也感谢同学给予的帮助zhouyuheng2003