夏晓光(loveJY)的博客

参考

1

2

例题

有一个数列 $a1,a2,…,an$，每个 $ai$ 都是小于 $2^m$ 的非负整数。

现在需要实现三种操作，格式说明如下：

• 1 x y w：对于所有 $x≤i≤y$，将 $ai$ 修改为 $ai⊕w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
• 2 x y w：对于所有 $x≤i≤y$，将 $ai$ 修改为 $w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
• 3：从 $a1,a2,⋯,an$ 中选出若干个数，使得选出的数异或和最大。请输出这个最大值。

这里 $\oplus$ 表示按位异或运算，$x1,x2,⋯,xl$ 的异或和是指 $x1⊕x2⊕⋯⊕xl$。

$n,m,q\leq 2e3$

对于操作1,区间异或等价于差分后单点的异或修改

因为在线性基上,我们任何操作都只需要保证操作后每个数仍能被区间中的数异或表表示出来即可,在这样做之后,任何区间信息还是能够被$a_1$+所有其他异或操作表示,所以还是对的

对于操作2,我们不难发现等价于单点修改两个数,然后中间的数全部删掉

那么问题在于如何单点修改线性基

并不困难,离线做法我们可以线段树分治,然后只需要支持回溯,开$O(nlogm)$的空间即可

在线做法可以考虑线性基的性质

尽量的让秩尽可能高

线性无关组中有被异或的包括x

矩阵不需要降秩,我们直接拿出那个向量作为x向量,然后用它消元消掉其他向量信息即可,这样x相当于信息被消掉了,同时矩阵没有发生本质变化,相当于用那个向量代替了x向量,再将那个向量插入即可

如果真的删除x,要把原来向量打标记

线性相关组中有被异或的包括x

矩阵降秩

考虑拿出最小的且包含x的向量

最小的原因是我们要消其他的向量的时候,要保证其最高位仍然是x!

于是我们拿这个向量把所有其他的包含x的都异或一次消掉x,包括他自身,相当于消掉了他自己

之后让这个向量成为x即可,具体的直接插入即可