线性基（这里是异或线性基）是对于序列 \(a_1 ... a_n\) 满足以下条件的一个极小集合 \(\mathrm S\)：
-
\(S\) 中的所有元素可以通过异或表示出 \(a\) 中的所有元素。
-
\(S\) 在满足第一个条件的情况下，集合大小最小。
进一步的，可以推出以下性质：
-
\(S\) 中任意元素的异或和不等于 \(0\)。
-
\(S\) 的大小至多为 \(\log \max{a_i}\)。
第二个性质将在插入时自然给出。
基本操作：
- 插入：假设现在要插入的数是 \(x\)。考虑记 \(bs_i\) 是以第 \(i\) 位为最高 \(1\) 位的基底。不难发现，假如当 \(x\) 遍历到第 \(i\) 位时，且 \(x\) 的第 \(i\) 位为 \(1\)，该位的 \(bs_i\) 为空，则 \(x\) 无法被表出，原因是再向下遍历则无法在更改这一位。否则 \(x\) 必须要异或上该位。若最后 \(x\) 变为 \(0\)，其实就是 \(x\) 已经可以被表出，跳过即可。
qwq
void ins(int x){
for(int i = M; i >= 0; i--){
if(!(x & (1ll << i))) continue;
if(!bs[i]){bs[i] = x; return;}
x ^= bs[i];
}
}
- 查询最大值：假设现在要查询 \(a\) 中选出任意个数与 \(x\) 的异或最大值，从高位向低位考虑，显然后面选择的不会影响前面的，直接贪心即可。
qwq
int getmax(int x){
int ret = x;
for(int i = M; i >= 0; i--) ret = max(ret, ret ^ bs[i]);
return ret;
}
- 查询第 \(k\) 小的值：考虑类似于 \(\mathrm Trie\) 上二分的做法，首先将所有的 \(bs\) 变成任意两个都无交的形式，从高位向低位考虑，容易发现，假设这一位选择 \(1\)，则排名区间就变成了 \([1, 2 ^ {i - 1}]\)，否则是 \([2^{i - 1} + 1, 2^i]\)。然后二分就完了。
qwq
0 void rebuild(){
for(int i = 0; i <= M; i++){
for(int j = i - 1; j >= 0; j--){
if(bs[i] & (1ll << j)) bs[i] ^= bs[j];
}
} tot = 0;
for(int i = 0; i <= M; i++) if(bs[i]) rbs[++tot] = i;
}
int kth(int x, int k){
int ret = x;
for(int i = tot; i >= 1; i--){
int sz = (1ll << i - 1);
if(k <= sz){
if((x & (1ll << rbs[i]))) ret ^= bs[rbs[i]];
}
else{
if(!(x & (1ll << rbs[i]))) ret ^= bs[rbs[i]];
k -= sz;
}
} return ret;
}