资料出处：https://blog.csdn.net/a_forever_dream/article/details/83654397
https://blog.csdn.net/qaq__qaq/article/details/53812883
基础操作：
定义
设数集T的值域范围为[1,2n−1]。
T的线性基是T的一个子集A={a1,a2,a3,...,an}。
A中元素互相xor所形成的异或集合，等价于原数集T的元素互相xor形成的异或集合。
可以理解为将原数集进行了压缩。
性质
1.设线性基的异或集合中不存在0。
2.线性基的异或集合中每个元素的异或方案唯一，其实这个跟性质1是等价的。
3.线性基二进制最高位互不相同。
4.如果线性基是满的，它的异或集合为[1,2n−1]。
5.线性基中元素互相异或，异或集合不变。
维护
插入
如果向线性基中插入数x，从高位到低位扫描它为1的二进制位。
扫描到第i时，如果ai不存在，就令ai=x，否则x=x⊗ai。
x的结局是，要么被扔进线性基，要么经过一系列操作过后，变成了0。
bool insert(long long val) { for (int i=60;i>=0;i--) if (val&(1LL<<i)) { if (!a[i]) { a[i]=val; break; } val^=a[i]; } return val>0; }
合并
将一个线性基暴力插入另一个线性基即可。
L_B merge(const L_B &n1,const L_B &n2) { L_B ret=n1; for (int i=0;i<=60;i++) if (n2.d[i]) ret.insert(n2.d[i]); return ret; }
查询
存在性
如果要查询x是否存于异或集合中。
从高位到低位扫描x的为1的二进制位。
扫描到第i位的时候x=x⊗ai
如果中途x变为了0，那么表示x存于线性基的异或集合中。
最大值
从高位到低位扫描线性基。
如果异或后可以使得答案变大，就异或到答案中去。
long long query_max() { long long ret=0; for (int i=60;i>=0;i--) if ((ret^d[i])>ret) ret^=d[i]; return ret; }
最小值
最小值即为最低位上的线性基
long long query_min() { for (int i=0;i<=60;i++) if (d[i]) return d[i]; return 0; }
k小值
根据性质3。
我们要将线性基改造成每一位相互独立。
具体操作就是如果i<j，aj的第i位是1，就将aj异或上ai。
经过一系列操作之后，对于二进制的某一位i。只有ai的这一位是1，其他都是0。
所以查询的时候将k二进制拆分，对于1的位，就异或上对应的线性基。
最终得出的答案就是k小值。
void 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; }
模板：
struct L_B{ long long d[61],p[61]; int cnt; L_B() { memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); cnt=0; } bool insert(long long val) { for (int i=60;i>=0;i--) if (val&(1LL<<i)) { if (!d[i]) { d[i]=val; break; } val^=d[i]; } return val>0; } long long query_max() { long long ret=0; for (int i=60;i>=0;i--) if ((ret^d[i])>ret) ret^=d[i]; return ret; } long long query_min() { for (int i=0;i<=60;i++) if (d[i]) return d[i]; return 0; } void 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; } } L_B merge(const L_B &n1,const L_B &n2) { L_B ret=n1; for (int i=60;i>=0;i--) if (n2.d[i]) ret.insert(n1.d[i]); return ret; }