IOI2018 做题记

liu_cheng_ao 2018-09-15 9:54:42 2019-01-27 14:14:00

D2T3 Meetings

题意

给定一个序列 \{H_i\} ,每次询问一个区间的最小会议成本。离线。

区间 [x,y] 的最小会议成本定义为: \mathop{\min}\limits_{i=x}^y (\sum_{j=x}^i \mathop{\max}\limits_{k=j}^i H_k+\sum_{j=i+1}^y \mathop{\max}\limits_{k=i}^j H_k)

解法

考虑整个序列的解法:常见的思路是求出每个位置的答案并取最大值。利用单调栈可以维护,但这样每个位置依赖于前一个位置,不利于区间信息的合并和维护。不过后面可以看到这种方法的启发意义。

第二种思路是利用笛卡尔树。考虑原序列的最大值笛卡尔树 T ,对于 T 的每一个子树 T_x x 为树根),若其左右子树的大小分别为 \mathrm{size}_l,\mathrm{size}_r ,则左右子树中的每个点分别获得 H_x\cdot \mathrm{size}_r H_x\cdot \mathrm{size}_l 的贡献,最终的答案则是所有点的最小值。

可以注意到,在一棵子树和其中的所有子树全部计算完成后,其余部分对该子树中点的贡献均是相同的,也即不会影响它们的大小关系。故而,每棵子树在计算完成后只需关注代价最小者,如是递推而已。这样,我们获得了一个对子树(对应区间)封闭的算法。

然此方法仍需 O(QN) 之时间,准确而言,区间询问的笛卡尔树是 T 中区间部分的组合,共有 O(N) 棵子树。假若笛卡尔树满足某种平衡性质,如深度为 D ,那么此方法时间复杂度即为 O(QD)

笛卡尔树之形态是确定的,不能为此,不妨考虑以数据结构维护。一个区间对应的树为从其两端出发沿各自祖先中向彼此方向的链对应的所有子树形成之虚树,考虑此两点 x,y \mathrm{LCA} l (也即 l [x,y] H 之最大位置), x L 的部分可称左链,反之亦然。查询的最后一步便是以(二)中方法合并左右两侧的答案,这部分以及查询最值的部分仅需 O(1) 时间,已达下界而不再考虑。

我们注意到,无论区间如何,每个点左右链的父亲是确定的,二者各自形成一棵树,查询时即等价于在此二树上查询一条深度单调的链。进一步考察可以得到,左链中的右子树是确定的而右链中的左子树亦然,二者中 T_x 的答案仅与另一侧端点之位置成线性关系,可表为 \pm H_x\cdot l(r)+C_x ,其中 l,r 为左右端点,而我们需要查询链上该函数的最小值。这是一个凸包问题,可以维护。将链剖分共需总长度为 O(N \log N) O(N) 个部分,而查询时则需 O(\log^2 N) (采用以深度为键的可持久化方法或直接离线处理)至 O(\log^3 N) (重链剖分)时间不等。

这样的复杂度不尽人意,可见瓶颈在于树上数据结构——这种剖分方法已是下界了。我们重新审视计算过程,可以发现笛卡尔树并没有起到什么作用:左链,右链不依赖于树结构而存在,而我们对笛卡尔树递推做的子树仅保留一个值的「优化」反而成为限制树形结构的瓶颈了。实际上,每个位置的贡献仅仅是一个一次函数,而查询也只是区间最值而已。

并且,由(二)可得左右链中 l 以上部分的贡献对大小并无影响,都等于 l 对应该侧贡献的常数。那么,一次函数的信息是独立存在的,不需要依赖查询区间的端点而计算,我们要关注的仅仅是另一侧的端点而已。

至此,可以对(三)的计算方法稍作修改:以右链为例,从左向右依次处理每个位置并维护一次函数,这些函数的系数是会变化的,但 H 的单调栈中每段对应的系数却相同,对每一段的常数再行维护单调栈即可,和笛卡尔树一并单调栈维护,只保留树当前右链的一次函数即可。时间 O(N\log N+Q \log^2 N)

(四)中的方法时间没有变化,但可以注意到,每次查询一次函数的自变量实际上是相同的,我们只是在利用扫描线处理若干连续的分段一次函数而已。我们可以注意到,这些分段函数的系数永远关于原序列的下标单调递减,也即较新的分段函数一旦优于旧的,就永远如此,而其在区间查询中也包含前者。那么前者是没有必要存在的了。于是凸包是没有必要的,我们只需维护分段函数值与原序列中下标的单调栈即可。而单调栈中的元素也可分为若干段,与序列关于 H 的单调栈相对应。查询时在单调栈中查找 \mathrm{lower\ bound} 即可,时间 O(N\log N + Q \log N)

(五)的做法概括如下:

  1. 求得每个询问的区间最大值;

  2. 对原序列正、反方向分别进行扫描,维护单侧对当前位置贡献关于下标的单调栈 S ,和 H 关于下标的单调栈 S_H

  3. 在扫描到端点的时刻于单调栈中查询 \mathrm{lower\ bound} 并更新答案。

现在重新分析(五)的时间复杂度:步骤 1 采用适当的算法可得 O(N+Q) ,步骤 2 若将 S_H 对应 S 的每一段用链表维护并用下标的桶维护分段函数相交位置,则时间复杂度为 O(N) ,步骤 3 假若采用二分则需 O(\log N) 时间,但查询的为下标,且在步骤 2 中下标一旦移除就不再出现,只需用并查集维护下标对应的 \mathrm{lower\ bound} 集即可,时间复杂度则为 O(N\alpha N + Q)

总的时间复杂度为 O(N\alpha N+Q) ,瓶颈为并查集。

这个并查集只会合并序列中相邻两个集合并且操作是离线的。我们可以得出合并树,按照《A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION》介绍的算法可以做到线性时间。

于是我们达到了 O(N+Q) 的时间下界。

在线怎么做?直接套用的话要对「并查集」进行部分可持久化……不知道有什么优秀算法。

本文暂且抛砖引玉,等各位大佬来解答了。

共 2 条回复

LanrTabe

WC 2019 打卡。

XG_Zepto

WC 2019 打卡。