「愛ゆえの決断」

· · 算法·理论

「愛ゆえの決断」

给定一个长为 n 的序列,在线 q 次操作,每次操作是单点修改,或者查询一个区间中前缀最大值的信息。具体地,查询的时候返回一棵包含了区间中前缀最大值的持久化平衡树。此前的做法是 \log^2 n 的线段树套持久化平衡树,我们给出了一种时间复杂度为均摊 O(n+q\log n) 的做法。

在比较模型下这是最优的。考虑每次修改数组的第一项然后查询整个数组,就能规约到后继查询。

大概是驾驶众「神」做了一天的结果,读的时候按照个人想法简化了部分。感觉很震撼,因为这已经是完全脱离了 adhoc 小技巧的,十分复杂而优美的新结构。

「神」顺手造了一个 O(1) 拼接的持久化平衡树,感兴趣的同学可以到 part D 速览。

那么,我们开始吧。

我们对询问和修改做二进制分组,并且每 n 次重构一次。每个组内部将序列划分为若干段。这个组维护的序列是组中最后一次修改进行后的序列。其中每一段维护:

此外,在每个左端点(以下的端点都指左端点),我们还用 P 维护从这个点开始不断走出口直到走完,拼接过程中的前缀最大值序列得到的序列,称之为 W(l),用于应对查询。查询的时候只需要从右端点截断一下即可。

我们可能会给组加入端点,这时候可以利用 P 从已有的 W 拼接组内的前缀最大值序列得到新端点的 W(l)。这一操作有 O(n\log n) 次,因此 P 需要支持 O(1) 持久化地在开头加入一项。

我们需要支持这一操作:给最大的若干层加入某个端点。例如每次修改操作和查询操作的左端点,我们都会将其加入每个组的端点(因此每一组的端点是包含下一组的)。即区间会产生分裂。

如果分裂后区间的最大值位于右侧,那么右侧新区间的出口还是原区间,左侧新区间的出口就是右侧新区间。否则需要求出右侧新区间的出口。

这需要对每组做到线性时间复杂度。我们通过给每个段再维护一个候选序列做到这一点!

part A:候选序列

暂时只考虑每一段的最大值(关于如何动态维护每一段的最大值:事实上,我们甚至已经通过 P 维护了每段的前缀最大值序列,这部分之后会一并给出),将其记作序列 a。对于每个 a_i,找到后面第一个大于其的 a_j,然后记录 (i,j) 中的前缀最大值序列。可以发现每个点对应的序列的总长不超过 n,因为每个数只会出现在前面第一个大于其的数的候选序列中。

称其为候选序列,是因为考虑“分裂后区间最大值位于左侧”的 case,此时右侧新区间的出口只可能在候选序列中。我们应该在原区间的候选序列中找到右侧新区间的最大值的后继,从这个位置将候选序列分裂,分别作为右侧和左侧区间的候选序列。由于候选序列的总长不超过 n,不难发现,每次分裂操作如果分裂为大小分别是 a 和 b 的两部分,那么只要分裂的时间复杂度是 O(\log(\min(a,b))),总时间复杂度就是线性的。我们用 P 维护候选序列,并希望它能满足我们的要求。

这种 case 还会有出口需求,因此可能新建分段。这块的复杂度分析属于“给最大的若干层加入某个端点”的部分。

还有一个细节是,如果分裂后区间最大值位于右侧,那么左侧区间可能会加入某个候选序列。巧妙的是,由于左侧段首本身就是相应段的出口,左侧区间最大值加入的候选序列的位置一定在原区间最大值的前面。不过我们不实际执行中间插入,而是对每个段维护一棵二叉树表示其分裂过程。这样对应的候选序列在切到这个位置的时候,再将这棵二叉树拆开即可。具体来说,我们沿着二叉树中间切开,将路径左右两侧与路径长度同阶的段作为代表加入两侧的候选序列。

part B:重构和插入端点

操作还可能导致二进制分组重构。假设其中有 k 次修改 x_{1\dots k},那么将 x_{i},x_{i}+1 都列入端点。需要先求出每一段内部的前缀最大值序列。如果这一段是单点,即修改操作,那么直接新建;否则,我们从之前的层尝试得到这段区间的前缀最大值序列。

具体地,我们希望得到这一层 [l,r] 的前缀最大值序列。这类区间在这一层都没有被修改,所以可以考虑从上一层得到。由于这里的 l 都已经被加入了,我们可以考虑从 W(l) 截取得到。有个细节是,W(l) 在 P 中维护的,其实是这一层中经过的段的标号,而没有将每一段内部的前缀最大值序列都拿出来。

细心的同学立刻会发现关于 W(l) 的问题:W(l) 可能是很早建立的,换言之,它维护的块可能是旧的!也就是说,在我们插入一些端点之前,它就被建立了。最后一块有可能太大了,而我们需要查询一些更细的块。

不过,我们有解决方案——如果最后一块不完整,直接将这些小块逐个加入即可。一个显然的事实是,大小为 a 的组中只有 O(a) 个端点。假设我们正在重建大小为 a 的层,上一层的大小为 b,那么在此之前 b 这一块也就新建了 O(a) 个这类小块。

对于 P 所维护的 W(l),截取前 t 个块只需要 O(\log t) 时间。我们考虑这里产生的复杂度贡献。根据 \log 的凸性,以及需要截取的东西不相交,时间复杂度是 O(a\log(b/a))。对二进制分组的过程进行一些数学计算可知这是 O(q\log n) 的。

然后根据限制,还需要新建一些分段作为出口。与 part A 一样,有了每段内部的前缀最大值序列信息后,只需要找位置向若干层插入新的端点。

可见,我们对“向若干层插入端点”的操作有很强的需求(具体而言,我们尝试从上往下插入,如果当前层已经有这个端点就结束,否则递归)。除了重构的部分,还有询问的左端点。这时候需要求出右侧的新区间的前缀最大值序列。与上面的分析类似,访问过的小块数量仍然有保证,不过需要截取的东西不相交才能让复杂度是 O(q\log n)。

观察左侧区间对端点的需求,可以发现它的出口就是“前缀最大值序列分裂后,位于右侧的第一项”。因此这个位置也会分裂开,也即右侧区间会分裂。此时,其右侧区间的前缀最大值序列,就是原右侧区间的前缀最大值序列!所以我们只需要对中间的区间进行上一层的截取操作。这就说明,我们取回的上一层的段是不相交的,因为取回的下标互不相交。这就保证了时间复杂度。

part C:纯粹容器

现在我们要实现我们的喵喵小工具 P 了。

它有左中右三个部分。其中左侧和右侧都是大小至多为 3 的数组,存储基本元素;中间部分是将基本元素视为当前基本元素的二元组的递归 P。

执行插入的时候,先正常插入到对应的数组中。特别地。如果当前 P 中只有两个元素而且都在左/右数组中的一个,就将其中一个元素分到另一侧。如果一个数组满了,就将其中的两项打包递归插入中心。

先考虑候选序列中的查找部分。如果不在左数组也不在右数组就递归进入中心查找。由于非平凡的情况下左右数组都有数,因此能进入第 t 层说明 \log(\min(a,b))=\Omega( t)。

分裂也是类似的递归。不过,为了保证左右数组非空,还需要费一些功夫。假设我们在考虑右边的返回值,那么一些左侧的数组会被截断掉,那么我们需要将下层的数组的二元组拆出来;如果下层的左侧数组也只有一项,那么就需要递归。不过均摊时间复杂度仍然是正确的,将势能设为“只有一个元素的数组”数量即可。

最后是首项追加,需要持久化地 O(1),但是看起来无论如何插入都可能导致连锁插入。不过,插入不同的数对最终的影响都只是外层数组的一项。所以在插入前,我们执行一次“预插入”,此后每次插入都只需要 O(1)。

可以证明预插入的时间复杂度是均摊线性的!将势能设为有三个元素的数组个数(执行完预操作后忽视原结点的势能),每次执行完预插入后势能确实会减小,单次插入也确实只会增加一势能。于是就得到了一个奇怪的均摊持久化数据结构。

part D:返回结果

别忘了,我们返回的不是 P,而是一棵持久化平衡树。我们还得搓一个支持 O(1) 拼接的持久化平衡树。我们给出的这一结构是一般化的,而不依赖于 P 的合并结构。

一棵树由左侧和右侧组成。假设合并 X,Y, |X|\ge |Y|,我们就将 Y 插入 X 的右侧,反之亦然。右侧由三部分组成,记作 F,S,A。其中 F 是已经插入完毕的树,S 是一棵正在插入 F 的树,A 是正在等待插入的一些树,随意地合并起来。如果 |Y|\ge |S|,那么将 S,A,Y 整合为一棵树变成新的 S;否则让 Y 正常进入 A,继续将 S 插入 F 的过程执行 O(1) 步;如果 S 插入完毕了,就将 A 整个放到 S。这里 F 的平衡策略需要让插入的时间复杂度是 O(\log (|F|/|S|))(同时距离根的深度也是这个),而且不能拆开 S,可以这样设计:将 S 的权重设为 \max_{i=|F|+1}^{|F|+|S|}\text{lowbit}(i),维护一棵关于权重的大根笛卡尔树。可以在数轴上想象这棵笛卡尔树,插入的时候只需要沿着右链走即可。

考虑 Y 在每一时刻距此处根的距离。Y 在 A 中时,距离大约是队列长度,而队列长度不超过 O(\log (|F|/|S|)),|Y|<|S| 因此正确。在 S 中时只会受到“将 S,A,Y 整合”的影响,当然也是对的。

我们对 P 中每个元素和 P 本身维护一个其代表的平衡树,最后从 W(l) 给出的平衡树中截取出 \le r 的部分即可。如果希望给出的树更加平衡,需要将 A 改成斜二进制维护。