「CTSC2016」时空旅行 题解

问题重述与转化

我们有 $n$ 个时空构成一棵树（根为 $0$ 号时空），每个时空有一个已被殖民的星球集合。操作分为：

• 殖民：在某个时空的基础上，增加一个星球。
• 放弃：在某个时空的基础上，删除一个星球。

进行 $m$ 次查询：给定目标时空 $s$ 和固定 $x$ 坐标 $x_0$，我们需要在时空 $s$ 的星球集合中，选择一个星球 $B$，最小化花费：

$$\text{cost} = (x_0 - x_B)^2 + y_B^2 + z_B^2 + c_B$$

其中 $(x_B, y_B, z_B)$ 是星球坐标，$c_B$ 是调查花费。

由于 $y,z$ 坐标可以任意选择，最小化时 $y,z$ 取 $0$ 即可，因此问题简化为：

$$\text{cost} = (x_0 - x_B)^2 + c_B = x_0^2 - 2x_B x_0 + (x_B^2 + c_B) $$

对于一个固定星球 $B$，这是一个关于 $x_0$ 的二次函数：

$$f_B(x_0) = x_0^2 - 2x_B x_0 + (x_B^2 + c_B)$$

$x_0^2$ 是常数，因此最小化 $f_B(x_0)$ 等价于最小化：

$$g_B(x_0) = -2x_B x_0 + (x_B^2 + c_B)$$

核心思路

1. 问题转化

对于每个查询 $(s, x_0)$，我们需要在时空 $s$ 的星球集合中，找到使 $g_B(x_0)$ 最小的星球 $B$。
$g_B(x_0)$ 是关于 $x_0$ 的一次函数，斜率为 $-2x_B$，截距为 $x_B^2 + c_B$。

因此问题转化为：

• 维护每个时空对应的一次函数集合
• 对于查询 $(s, x_0)$，求这些函数在 $x_0$ 处的最小值

2. 关键观察

• 星球只在特定时空区间存在（从殖民到放弃）。
• 时空结构是树形，每个时空的星球集合是其祖先路径上所有操作的结果。
• 查询针对某个时空 $s$，即需要知道根到 $s$ 路径上所有有效星球对应的函数。

算法框架

3. 区间化处理

将每个星球的存在时间（在 DFS 序上）转化为一个时间区间 $[L, R]$。

• 殖民操作：在 $L$ 时间加入
• 放弃操作：在 $R$ 时间移除

这样，每个星球对应一个时间区间。当查询时空 $s$（DFS 序为 $dfn[s]$）时，需要所有包含时间 $dfn[s]$ 的星球。

4. 线段树维护凸包

使用线段树分治：

• 线段树每个节点维护一个凸包（下凸壳），存储在该节点对应时间区间内存在的所有一次函数。
• 插入一个星球时，将其对应的一次函数插入到线段树覆盖其存在区间的所有节点中。

对于一次函数 $y = kx + b$（这里 $k = -2x_B, b = x_B^2 + c_B$），在线段树节点中维护下凸壳。

5. 查询处理

对于查询 $(s, x_0)$：

• $x_0$ 固定，需要在凸包上找到使 $y = kx_0 + b$ 最小的点。
• 由于 $x_0$ 可能随查询变化，先按 $x_0$ 排序，这样在凸包上查找时可以单调移动指针。
• 从根到叶子，在每个线段树节点上用指针查询当前凸包的最小值。

实现细节

6. 数据结构

struct info {
    ll x, y; // 对应 k 和 b
    // 凸包相关运算
};
vector<info> t[N << 2]; // 线段树每个节点的凸包
int pos[N << 2]; // 每个节点当前最优位置指针

7. 主要步骤

1. DFS 预处理：计算每个星球的出现区间 $[L, R]$。
2. 线段树插入：将每个星球的一次函数插入对应区间。
3. 构建凸包：对每个线段树节点，排序并构建下凸壳。
4. 处理查询：按 $x_0$ 排序，在线段树上递归查询最小值。

8. 复杂度分析

• 预处理：$O(n \log n)$
• 凸包构建：总共 $O(n \log n)$ 个函数，每个节点排序建凸包
• 查询：$O(m \log n)$
• 空间：$O(n \log n)$

算法总结

本题的核心是将三维空间的最小距离问题，通过数学转化简化为一次函数最小值问题。再利用以下关键技巧：

1. 时间区间化：将树上的殖民/放弃操作转化为时间轴上的区间插入删除。
2. 线段树分治：高效处理区间存在性查询。
3. 凸包优化：对一次函数集合维护下凸壳，支持快速查询最小值。
4. 离线排序：将查询按 $x_0$ 排序，使凸包查询指针单调移动，保证复杂度。

难点突破

1. 问题转化：认识到 $y,z$ 坐标可优化为 $0$，将三维距离简化为 $x$ 坐标差的平方。
2. 函数表示：将每个星球表示为一个一次函数，将最小值问题转化为凸包查询。
3. 区间处理：将树形结构上的操作转化为线性时间轴上的区间，便于数据结构维护。
4. 实现技巧：凸包构建、指针单调移动、线段树分治等高级数据结构的综合应用。

这道题综合考察了问题转化、数学建模、数据结构设计等多方面能力，是一道典型的CTSC级别难题，需要选手具备扎实的算法基础和灵活的思维。