「愛ゆえの決断」
「愛ゆえの決断」
给定一个长为
在比较模型下这是最优的。考虑每次修改数组的第一项然后查询整个数组,就能规约到后继查询。
大概是驾驶众「神」做了一天的结果,读的时候按照个人想法简化了部分。感觉很震撼,因为这已经是完全脱离了 adhoc 小技巧的,十分复杂而优美的新结构。
「神」顺手造了一个
那么,我们开始吧。
我们对询问和修改做二进制分组,并且每
- 这一段后面,第一个大于这一段的最大值的位置。我们要求这个位置必须是某一段的段首,否则在这里分段。将其称之为出口。可以发现出口导致的分段不会导致新的出口需求。也即如果我们新增一个分段,只需要考虑一次出口导致的分段。
- 这一段内部的前缀最大值序列,用某种容器维护。我们会大量用到这个容器,不妨将其称为纯粹容器,下面用 P 指代。
此外,在每个左端点(以下的端点都指左端点),我们还用 P 维护从这个点开始不断走出口直到走完,拼接过程中的前缀最大值序列得到的序列,称之为
我们可能会给组加入端点,这时候可以利用 P 从已有的
我们需要支持这一操作:给最大的若干层加入某个端点。例如每次修改操作和查询操作的左端点,我们都会将其加入每个组的端点(因此每一组的端点是包含下一组的)。即区间会产生分裂。
如果分裂后区间的最大值位于右侧,那么右侧新区间的出口还是原区间,左侧新区间的出口就是右侧新区间。否则需要求出右侧新区间的出口。
这需要对每组做到线性时间复杂度。我们通过给每个段再维护一个候选序列做到这一点!
part A:候选序列
暂时只考虑每一段的最大值(关于如何动态维护每一段的最大值:事实上,我们甚至已经通过 P 维护了每段的前缀最大值序列,这部分之后会一并给出),将其记作序列
称其为候选序列,是因为考虑“分裂后区间最大值位于左侧”的 case,此时右侧新区间的出口只可能在候选序列中。我们应该在原区间的候选序列中找到右侧新区间的最大值的后继,从这个位置将候选序列分裂,分别作为右侧和左侧区间的候选序列。由于候选序列的总长不超过
这种 case 还会有出口需求,因此可能新建分段。这块的复杂度分析属于“给最大的若干层加入某个端点”的部分。
还有一个细节是,如果分裂后区间最大值位于右侧,那么左侧区间可能会加入某个候选序列。巧妙的是,由于左侧段首本身就是相应段的出口,左侧区间最大值加入的候选序列的位置一定在原区间最大值的前面。不过我们不实际执行中间插入,而是对每个段维护一棵二叉树表示其分裂过程。这样对应的候选序列在切到这个位置的时候,再将这棵二叉树拆开即可。具体来说,我们沿着二叉树中间切开,将路径左右两侧与路径长度同阶的段作为代表加入两侧的候选序列。
part B:重构和插入端点
操作还可能导致二进制分组重构。假设其中有
具体地,我们希望得到这一层
细心的同学立刻会发现关于
不过,我们有解决方案——如果最后一块不完整,直接将这些小块逐个加入即可。一个显然的事实是,大小为
对于 P 所维护的
然后根据限制,还需要新建一些分段作为出口。与 part A 一样,有了每段内部的前缀最大值序列信息后,只需要找位置向若干层插入新的端点。
可见,我们对“向若干层插入端点”的操作有很强的需求(具体而言,我们尝试从上往下插入,如果当前层已经有这个端点就结束,否则递归)。除了重构的部分,还有询问的左端点。这时候需要求出右侧的新区间的前缀最大值序列。与上面的分析类似,访问过的小块数量仍然有保证,不过需要截取的东西不相交才能让复杂度是
观察左侧区间对端点的需求,可以发现它的出口就是“前缀最大值序列分裂后,位于右侧的第一项”。因此这个位置也会分裂开,也即右侧区间会分裂。此时,其右侧区间的前缀最大值序列,就是原右侧区间的前缀最大值序列!所以我们只需要对中间的区间进行上一层的截取操作。这就说明,我们取回的上一层的段是不相交的,因为取回的下标互不相交。这就保证了时间复杂度。
part C:纯粹容器
现在我们要实现我们的喵喵小工具 P 了。
它有左中右三个部分。其中左侧和右侧都是大小至多为
执行插入的时候,先正常插入到对应的数组中。特别地。如果当前 P 中只有两个元素而且都在左/右数组中的一个,就将其中一个元素分到另一侧。如果一个数组满了,就将其中的两项打包递归插入中心。
先考虑候选序列中的查找部分。如果不在左数组也不在右数组就递归进入中心查找。由于非平凡的情况下左右数组都有数,因此能进入第
分裂也是类似的递归。不过,为了保证左右数组非空,还需要费一些功夫。假设我们在考虑右边的返回值,那么一些左侧的数组会被截断掉,那么我们需要将下层的数组的二元组拆出来;如果下层的左侧数组也只有一项,那么就需要递归。不过均摊时间复杂度仍然是正确的,将势能设为“只有一个元素的数组”数量即可。
最后是首项追加,需要持久化地
可以证明预插入的时间复杂度是均摊线性的!将势能设为有三个元素的数组个数(执行完预操作后忽视原结点的势能),每次执行完预插入后势能确实会减小,单次插入也确实只会增加一势能。于是就得到了一个奇怪的均摊持久化数据结构。
part D:返回结果
别忘了,我们返回的不是 P,而是一棵持久化平衡树。我们还得搓一个支持
一棵树由左侧和右侧组成。假设合并
考虑
我们对 P 中每个元素和 P 本身维护一个其代表的平衡树,最后从