问题分析

我们需要找到一个排列 $p$，使得：

1. 满足依赖关系：所有延伸算法必须在它们依赖的基础算法之后学习
2. 最小化相邻算法价值差的绝对值之和：$w(p) = \sum_{i=1}^{n-1} |w_{p_i} - w_{p_{i+1}}|$

这是一个带约束的路径优化问题，约束条件形成了一棵依赖树。

算法思路

1. 核心观察

将算法按价值排序后，最优解具有以下结构特征：

• 整体上价值单调递增或递减
• 在依赖关系的约束下，某些区间需要重复遍历

2. 关键数据结构

• 排序数组：$id[]$ 按价值排序的算法编号
• 依赖关系：$lnk[i]$ 表示延伸算法 $i$ 依赖的基础算法
• 差分数组：$dif[]$ 标记哪些位置受到依赖关系影响
• 排名数组：$rk[i]$ 记录算法 $i$ 在排序后的位置

3. 算法流程

预处理阶段

1. 将所有算法按价值排序
2. 建立依赖关系的排名映射

约束分析

对于每个延伸算法 $i$：

• 如果 $rk[i] < rk[lnk[i]]$，说明在排序序列中，延伸算法出现在依赖算法之前
• 使用差分数组标记这个约束影响的区间

最优路径计算

通过动态规划寻找最优的"折返点"：

• 考虑从最小值到最大值再返回的路径
• 在约束区间内可能需要重复遍历某些段
• 计算不同折返策略的代价，取最小值

构造解

根据找到的最优折返点：

1. 先处理左侧的基础算法
2. 按依赖关系插入延伸算法
3. 处理中间受约束的区域
4. 最后处理右侧的基础算法和延伸算法

4. 双向处理

算法执行两次：

1. 第一次按价值升序处理
2. 第二次将价值取负后按升序处理（相当于原价值的降序）
3. 取两次中的最优解

复杂度分析

• 排序：$O(n \log n)$
• 约束分析：$O(n)$
• 路径计算：$O(n)$
• 构造解：$O(n)$
• 总复杂度：$O(n \log n)$，适合 $n \leq 10^6$ 的数据范围

算法优势

1. 巧妙的问题转化：将依赖约束转化为区间标记问题
2. 双向搜索：同时考虑递增和递减两种最优路径模式
3. 差分数组优化：高效处理区间约束
4. 贪心构造：在保证正确性的前提下快速构造解

总结

本题的解法展示了如何将带约束的排列优化问题转化为排序后的路径选择问题。通过分析依赖关系的区间影响，并结合动态规划寻找最优折返策略，算法在 $O(n \log n)$ 时间内解决了大规模实例。

核心技术点：

• 依赖关系的区间化处理
• 双向最优路径搜索
• 差分数组标记约束
• 贪心解构造