[线性基学习笔记]

定义

设数集$T$的值域范围为$[1,2^{n}-1]$

$T$的线性基是$T$的一个子集$A=\{x_1,x_2,x_3,…,x_n\}$。

$A$中元素互相$xor$所形成的异或集合,等价于原数集$T$的元素互相$xor$形成的异或集合。
可以理解为将原数集进行了压缩。

维护

插入

想在线性基中插入数$v$,从高到低扫描器为$1$的位,若到$i$时$x_i$不存在,就加入线性基,否则异或上$x_i$。

最后$v$要么变为$0$(其在线性基中),要么被加入线性基。

合并

将每一个线性基插入即可。

查询存在

想在线性基中查询数$v$是否存在,类似插入的做法,若最后变为$0$则在线性基中。

查询最大值

从高到低,若异或上$x_i$可以使得答案变大就异或。

查询最小值

输出最小的$x_i$。

查询第$k$小

如果要查询第$k$小,我们必须要保证每位独立,即对于$i<j$,若$x_j$的第$i$位上是$1$,我们将$x_j$异或上$x_i$

然后将$k$二进制拆分,异或上对应位置的的$x_i$。

 

例题

BZOJ4184 shallot

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注