插入
设插入\(k\)，\(k\)的最高位为\(l\)
- 若线性基的第\(l\)位为\(0\)，则直接在该位插入\(k\)，结束
- 若线性基的第\(l\)位已经有值\(base_i\)，则\(x = x\oplus a_i\)，重复上述操作。（\(\oplus\)表示异或）
int base[N+1];
il void insert(int k){
for(ri int l=N;~l;--l){
if(k>>l){
if(!base[l]){base[l]=k;break;}
k^=base[l];
}
}
return;
}
同理可判断能否通过原数列异或得到一个数\(k\)
il bool check(int k){
for(ri int l=N;~l;--l){
if(k&(1<<l)){
if(!base[l]) return 0;
k^=base[l];
}
}
return 1;
}
查询异或最值
- 查询最小值：考虑插入的过程，因为每一次跳转操作，xx的二进制最高位必定单调降低，所以不可能插入两个二进制最高位相同的数。而此时，线性基中最小值异或上其他数，必定会增大。所以，直接输出线性基中的最小值即可。
- 异或最大值：从高到低遍历线性基，考虑到第\(l\)位时，如果当前的答案\(as\)第\(l\)位为\(0\)，就将\(as\)异或上\(base_i\)；否则不做任何操作。显然，每次操作后答案不会变劣，最终的\(as\)即为答案。
il int ask_min(){
for(ri int l=0;l<=N;++l){
if(base[l]) return base[l];
}
return -1;
}
il int ask_max(){
int as=0;
for(ri int l=N;~l;--l){
as=max(as,as^base[l]);
}
return as;
}