困难优化 题解

思路

把每条原线段看成一个结点：若线段 $v$ 被线段 $u$ 直接包含，就令 $v$ 成为 $u$ 的儿子。层状性质保证得到一个有序森林；按左端点排序并维护包含栈即可建树。

所选子线段内部不相交，所以目标值等于这些子线段并集的总长度。最优解的端点可以移动到某个原端点而不变差。对结点 $u$，它的儿子从左到右把 $[L_u,R_u]$ 分为若干空隙；祖先的子线段在 $u$ 的子树中只需表现为若干段“预留区间”。合并相邻部分时，只需知道预留段数，以及是否有预留段接触当前范围的左右端点。

做法

子任务 1：排列枚举

任意合法构造按位置从左到右给出了 $n$ 条线段的一个排列。枚举所有排列后，沿整数坐标做动态规划：若上一条已在位置 $t$ 结束，当前线段最早从 $\max(t,L_i)$ 开始；枚举其右端点即可。记录前驱可恢复构造。复杂度为 $O(n!\,nC^2)$，其中 $C$ 是端点跨度。

子任务 2：子集调度 DP

令 $f[S][x]$ 表示已经按某种顺序放置集合 $S$ 中的线段，最后一条在坐标 $x$ 结束时的最大长度和。向未使用线段 $i$ 转移。对固定的新右端点，最优左端点由 $x\le L_i$ 与 $x>L_i$ 两类前缀最大值求出，因此每个状态可在线性坐标范围内完成转移。复杂度为 $O(2^n nC)$。

子任务 3：原线段两两不交

直接选取每条完整原线段。它们已经互不相交，并且任何构造在第 $i$ 条线段内的长度都不超过 $R_i-L_i$，故这一定最优。

子任务 4：树形预留区间 DP

定义

为处理完 $u$ 的整棵子树后，给祖先保留 $k$ 个互不相交区间时的最大已覆盖长度；$a,b$ 分别表示其中是否有一段接触 $L_u,R_u$。

从左到右合并儿子。设当前合并结果右端标志为 $b$，儿子状态左端标志为 $a'$：

• 两边的预留段数相加；若 $b=a'=1$，可以选择把接触边界的两段合并，段数减一；
• 儿子后的空隙可以不保留，也可以新建一段预留区间；
• 若儿子的右端标志为真，新空隙还可以直接并入该预留段。

合并完全部儿子后，结点 $u$ 必须拿走一段预留区间作为自己的答案，因此把段数减一。一般可优先拿走内部预留段；当只剩左右边界段时，枚举拿走哪一侧。叶子直接把完整原线段作为自己的区间。

预留段数只需保留到 $\min(\operatorname{depth}(u),\operatorname{size}(u))$。树上背包中任意两个结点只会在其最近公共祖先处共同贡献一次，故总复杂度为 $O(n^2)$。

恢复时重新执行每个结点的儿子背包并记录所选转移，得到恰好 $n$ 个互不相交的预留区间。再按区间长度和原线段长度从小到大贪心匹配：把当前预留区间交给能包含它的最短未使用原线段。

复杂度

满分算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

正确性证明

首先，层状集的直接包含关系构成森林，且不同儿子线段从左到右互不相交。

对任意结点 $u$，在其子树范围内，祖先所选子线段与儿子子树产生的已占用部分相交后，只可能形成若干个按顺序排列的预留区间。它们对更高层转移的全部影响只有段数，以及是否接触 $L_u,R_u$；内部每段的具体身份不会影响可合并性。因此 $dp[u][k][a][b]$ 包含了充分信息。

合并一个儿子时，两个相邻部分之间只有“不覆盖空隙”“把空隙作为新预留段”“把空隙并入右侧接触段”三类情况；若两侧都接触公共边界，又恰有合并或不合并两种选择。转移逐一枚举了这些互斥且完备的情况，所以合并结果最优。

随后结点 $u$ 从预留集合中取走恰好一段，保证每个结点最终获得一个非空子线段。内部段不涉及边界，优先取走不会限制祖先；只有预留段数很少且仅剩边界段时才需要显式枚举左右选择，转移已覆盖这些特殊情况。由树高归纳，每个 $dp$ 状态都达到其定义下的最优值。根状态不再给外部保留区间，故其值就是整棵树的最优值；各棵树原本互不相交，求和即为全局最优。

最后，恢复得到的区间两两内部不交，并分别能被某条原线段包含。按长度从小到大将预留区间分配给最短可包含它的原线段，是层状包含关系上的标准交换贪心：若较短原线段可容纳当前区间而被留给更大的区间，交换二者不会破坏包含关系。故一定能完成一一匹配，并得到输出顺序对应的最优合法构造。