线性基学习笔记

我废话怎么这么多wwwwwwwwwww\(\color{white}地址\)

rebuild

思想就是使满足线性基的条件下，使每一个二进制位只在一个位置上为 1。

可以用高斯消元直接处理出，也可以处理出任意一组线性基后从后往前扫一遍，如果 \(a_i\) 第 \(j\) 位上为 \(1\)，则 \(a_i\oplus a_j\to a_i\)。此时如果用一个二进制数表示取线性基中的哪些数异或起来，记作 \(b_S\)，则 \(b\) 单调上升。

queryKth（去重）

将一组线性基 rebuild 后的性质很好，所以结果即为 \(b_k\)。

queryRank

二分+queryKth 是 \(O(\log^2 n)\) 的。但是可以考虑类似倍增的东西，rebuild 后从后往前扫一遍，异或之后值不超过 \(x\) 就异或上并加上排名贡献。\(O(\log n)\)。

merge

直接将 \(b\) 中每个往 \(a\) 做一次 insert。

Lemma 1

\(n\) 个数组成大小为 \(s\) 的线性基，组合出 \(2^s\) 个不同的数，每个出现 \(2^{n-s}\) 次。

Proof：考虑在不在线性基中的数中选择一个子集异或和为 \(x\)，则在线性基中一定有一种方法组合出异或和 \(x\) ，否则子集中应有一些数会插入线性基。并且只有一种方法，否则不满足线性基条件。则得到为 \(0\) 的异或和后，再使用线性基内的数组合一下就可以得到这 \(2^s\) 个数中的任意一个。