P5607 更优秀的做法

chenxinyang2006 · 2024-04-23 00:16:51 · 题解

其他题解已经介绍了本题事实上等价于单点修改、求一个区间的线性基信息。这个问题以往的常规做法是直接建线段树，对每个节点维护对应区间的线性基信息，认为时间复杂度是 O(n \log^2 V + m \log n \log^2 V)（事实上关于 n 的复杂度可以分析到更低）。现在给出一种时间复杂度为 O(n \log \log V \log V + m (\log n \log V+\log^2 V)) 的做法。

我们先来研究一些更简单的问题。

• 维护 n 个集合，初始均为空。支持向某个集合插入一个数，以及查询一段前缀的线性基信息。

  这个问题通过使用被称为区间线性基的技巧可以做到插入查询均为 O(\log V)。“区间线性基” 其实就是说我们注意到如果改变插入集合中所有数的顺序，线性基的数组事实上也会随之改变。因为我们希望查询前缀信息，如果是以编号从小到大的顺序将所有数插入线性基，并在线性基上额外记录占据这一位的数原本的编号是什么，只要只关注线性基上所有对应编号 \le r 的位，就可以得到 [1,r] 的线性基信息。当然事实上插入是按照时间顺序（操作给出的顺序）进行的，可以这样描述要解决的问题：有一个 (t_i,a_i) 二元组集合 S，你需要求出 f(S) 表示把所有二元组按照 t_i 从小到大排序后，依次将 a_i 插入到线性基后，线性基的形态。

  可以发现假设你知道 f(S)，要再向 S 中插入一个新的二元组，求出新的 f(S')，通过对 f(S) 进行一些调整，这个过程是可以 O(\log V) 完成的。

  这部分内容也可以参考 CF1100F 的题解。

• （P4839）维护 n 个集合，初始均为空。支持向某个集合插入一个数，以及查询一段区间的线性基信息。

  众所周知线性基是可合并的：把一个线性基的所有元素插入到另一个线性基就行，合并一次 O(\log^2 V)。这题的常规做法就是建线段树，然后把区间划分为 \log n 个线段树上的节点，把所有节点维护的线性基信息合并起来，要做 \log n 次合并。

  但我们其实有 “区间线性基” 的技巧，这使得我们可以在只维护了整体信息的情况下提取出前缀信息，所以这个 \log n 次合并能不能做得更好呢？

  事实上可以：建线段树，对每个线段树上的节点，如果它是一个左儿子，维护对应区间的后缀线性基；如果它是一个右儿子，维护对应区间的前缀线性基；对根什么都不维护。

  查询时，考虑何时查询区间首次被 mid 切开，设此时线段树节点管辖 [l,r]，查询区间是 [L,R]，我们需要的线性基信息可以由 [L,mid],[mid+1,R] 合并而来，而这两段区间分别是左儿子对应区间的后缀和右儿子对应区间的前缀，信息都被我们维护了，只需要一次 O(\log^2 V) 的合并即可。这里找查询区间首次被 mid 切开的位置其实是求一次 LCA，理论上不是瓶颈。

  修改时，对所有管辖被修改位置的线段树上节点，向这个节点的前/后缀线性基做一次插入即可。

  所以这样是修改 O(\log n \log V)，查询 O(\log^2 V) 的。

• （本题）维护一个长度为 n 的序列 a。支持单点修改，查询一段区间的线性基信息。

  看上去和上一题差不多？但如果你想要沿用上一题的做法，你发现你相当于要求解这样的子问题：

• 维护一个长度为 n 的序列 a，支持单点修改，查询前缀线性基信息。

  事实上如果不要求查询前缀线性基信息，而是维护全局线性基信息，并且允许离线的话，仍然是可以保持插入查询 O(\log V) 的时间复杂度的：考虑上面描述的维护二元组集合 S 的问题，t_i 事实上也不一定要是编号，我们将其改为每个元素被删除的时间（显然单点修改可以看作删除一个元素再加入一个元素），即维护时间意义上的后缀线性基，就可以带删除地维护全局线性基信息。

  这部分内容也可以参考 这篇博客。

  但这种方法显然无法沿用到带删查询前缀线性基信息上：每个值这样会拥有 “前缀” 对应的编号信息和 “被删除的时间” 两维，我们相当于希望求一个前缀矩形，即 x,y 坐标均小于等于对应上界的所有点的线性基信息，显然无论对点集如何排序都不能总用一段前缀表示这个矩形信息。

  为此我们需要引入一个阴间技巧：带删线性基。这部分内容参考自 memset0 的博客。

  我们还是考虑上面的子问题，不过现在要求强制在线，该怎么办？

  还是把修改看作一次删除一次插入，主要是考虑删除如何进行？我们额外对所有序列中的元素维护 resp_i 是一个 n 位二进制数，表示 a_i 如果要写作一些线性基中的元素的异或和，应包含由原序列的哪些元素。以及对线性基的每一位维护 wresp_i 也是 n 位二进制数，表示这个值要写成一些线性基中元素的异或和，应包含原序列哪些元素。

  这里明确一下概念：线性基的数组上每一位的值事实上是不直接对应原序列的值的，是原序列一些元素的异或和。假设我们按编号顺序插入序列中所有元素，会有一些元素插入成功，最后填上了线性基数组的某一位，接下来我们称所有这样插入成功的元素的原始值构成的集合为一组 标准基（这个概念是我瞎定义的）。那么原序列所有子集的异或和都可以被唯一表示为标准基的一个子集的异或和，resp_i,wresp_i 就分别状压了 a_i 和 w_i 进行这样分解后的子集结果，这里 w_i 指线性基数组第 i 位的值。

  可以注意到如果确定了标准基有哪些元素（和这个元素来自的下标），事实上可以构建任意前缀的线性基信息，当然这要消耗 O(\log^2 V) 时间。

  要删除 a_i，如果 a_i 不在标准基内很简单。假设 a_i 在标准基内，枚举所有不在标准基内的元素 a_j，如果 resp_j 含有 i，说明可以将 a_j 写成 a_i 与一些其他标准基内元素的异或和，换句话说也就是可以将 a_i 写作 a_j 和一些其他标准基内的元素的异或和，所以可以考虑把 a_i 踢出标准基然后把 a_j 加入标准基。这会对所有 resp_i,wresp_i 产生一些影响：记 msk = 2^j \oplus resp_j，如果本来含有 i 这一位，需要异或上 msk。而 w 数组可以发现其实可以不变：因为 w 数组只要求线性无关以及子集异或和恰好能表示出 a 序列所有子集异或和，而 a 序列子集异或和构成的集合在这个 case 事实上不变。

  这里根据标准基的定义，可以发现要选最小的可行的 j。

  但如果任何 resp_j 都不包含 i 呢？这说明除了 i 以外，任何 a_j 在标准基内的表示都不需要 i，所以可以直接将 a_i 踢出标准基。这里显然就不需要修改 resp 序列了，但 wresp 序列和 w 序列要怎么修改？考虑找到 wresp 最低的一位 wres_q 包含 i，将高于 q 的所有包含 i 的 wresp 位的值异或上 wres_q，w 也做相应处理。这样就可以保证所有 w 序列包含的值都在删去 a_i 后仍然可以被表示为 a 序列子集异或和了，并且注意到因为 q 是最低的 wresp 包含 i 的位，所以更高的 w 序列的位的值不会受影响（因为只异或上了 w_q，w_q 的最高位更低），最后将 w_q,wresp_q 置零即可。

  要插入 a_i，因为我们标准基必须是按编号顺序插入时插入成功的 a_i 构成的集合。所以注意如果实际上（也就是最后）插入 a_i 失败了，不代表 a_i 不在标准基中：把 a_i 写成标准基子集异或和的形式，如果这个子集编号最大的编号大于 i，那么应该把那个值踢出标准基，把 i 加入标准基，这对 resp,wresp 的影响需要相应处理。把 a_i 写成标准基子集异或和的形式通过 wresp 数组即可完成。

  于是我们可以 O(\dfrac{n^2}{w}) 插入、删除元素。事实上注意到 resp 只有固定的至多 \log V 位有值（因为是标准基的子集，标准基大小不超过 \log V ），应该可以优化到 O(\dfrac{n \log V}{w}) 也就是 O(n) 插入删除元素。（因为我们这里都是认为集合内所有元素能直接被一个 word 存下，也就是 \log V < w 的）

  但这个做法看着还是很没用：每次直接暴力重建线性基都是 O(n \log V) 的，搞了半天比暴力去了一个 \log V，看上去实在太蠢了。单次 O(n) 地解决上面的子问题并没有意义。

  为此，我们需要关注算法的整体性。

考虑这样一个事实：假设你维护了线段树上所有节点的一组标准基，要支持单点修改。你其实不必认为某个维护 [l,r] 的节点要带删地维护长为 r-l+1 的序列的标准基，而可以认为它其实要维护它左右儿子的标准基拼起来得到的序列，的标准基，当然对于叶子还是维护它唯一那个值的标准基。

而后者的长度就只有至多 2\log V 了，我们那个 O(n) 的算法就非常有用武之地了。

于是我们得到了最终算法：对线段树上所有节点维护正向/反向的标准基，建立是 trivial 的，叶子节点直接拿过来，非叶子节点将左右儿子的标准基的各个元素依次插入即可。修改时，相当于先对叶子的值进行修改，这会对它两个方向的标准基造成若干次插入和删除，而这些插入和删除在这个叶子的父节点看来，相当于父节点要维护的序列发生了若干次插入和删除，依次类推。

然后我们知道事实上对一个序列的值做单点修改，对这个序列的标准基产生的影响是进行 O(1) 次插入和删除。所以把这些插入和删除事件做一些消去（要插入和删除相同的值可以都消去）就可以保证插入和删除事件每层都只进行 O(1) 次。

查询时，像上一个例题一样找到首次切开的位置 mid，相当于要查询 [L,mid],[mid+1,R] 两段区间的线性基信息。比如 [mid+1,R] 的部分，其实直接取出 [mid+1,r] 这一线段树节点维护的标准基中，所有编号 \le R 的元素，插入一个新的线性基即可。

这样修改和查询的复杂度都与上一例题保持不变：修改 O(\log n \log V)，查询 O(\log^2 V)。

然后我们对建立的复杂度进行更精细的分析：如果 n=2^k 的话，距离叶子为 d 的节点管辖的区间长度为 2^d，那么其建立时至多要向线性基插入 \min(2^{d-1},\log V) 个元素，而这样的节点有 2^{n-d} 个。

把 d \le \log \log V 的层估计成 2^{d-1}，每一层插入次数总和不超过 n。d > \log \log V 的层估成 \log V，这些层的总节点数不超过 2^{k-d+1}。这样前半部分是 O(n \log \log V) 次插入，后半部分是 O(n) 次插入，显然时间复杂度不超过 O(n \log \log V \log V)。事实上这里两边仍然不平衡，应该可以稍微更优一点。

最后还有一个优化：扔掉线段树上所有管辖区间长度 \le \log V 的节点，只有查询区间长度 \le \log V 时其才会在一个管辖区间长度 \le \log V 的节点处被切开，那么这些查询是可以直接暴力的。这样在时间复杂度上是常数优化，在空间复杂度上除了一个 \log V，做到了线性空间。

所以最后我们得到了这样一个做法：时间复杂度 O(n \log \log V \log V + m(\log n \log V + \log^2 V))，空间复杂度 O(n)，并且可以强制在线。

给出一份可能实现得并不好的代码：

code