AC. 梦想

frank_c1

[CTSC 2016] 时空旅行

发布于2017年04月24日 | 暂无评论 | 442阅读 | ,线段树

题意简述

n个时空,第i个时空继承于第f_i个时空,并在此基础上加入或删除了某一个星球。

星球以三维坐标(x_i,y_i,z_i)表示,且每个星球有一个参数c_i

q个询问。每次选定一个时空s和一个平面x = x_0。求从该平面出发可到达的花费最小的星球。

到一个星球i的花费为(x_0 - x_i) ^ 2 + c_i

1 \le n, q \le 5 \times 10 ^ 5, 0 \le f_i \lt i, |x_i, y_i, z_i| \le 10 ^ 6, 1 \le c \le 10 ^ {12}

算法讨论

输入的y, z坐标明显是酱油的。简化一下题意,就是有一棵时空树,每次选择一个点,询问x_0,求其中所有星球i(x_0 - x_i) ^ 2 + c_i的最小值。稍微化简一下可以发现

(x_0 - x_i) ^ 2 + c_i = -2x_i x_0 + x_i ^ 2 + c_i + x_0 ^ 2

对于每个i,我们忽略x_0 ^ 2这一项后可以看出这是关于x_0的一条直线。

那么如果只有一个时空,我们可以选择把直线建成上凸壳,在上面二分。

对于树状结构的时空,有什么性质可以运用吗?观察发现,每个加入的星球生效的范围都是DFS序上的若干段区间,且区间的总个数是O(n)的。也就是说,我们需要支持在序列上插入直线,询问某位置上代入某值x_0的最小值。

这启发我们使用线段树。由于只有单点询问可以标记永久化。我们把每条直线定位到O(\log n)个结点上。对于一个询问,我们查询叶子到根的所有结点,在凸壳上二分。这个算法的复杂度是O(n \log ^ 2 n)的。

考虑进一步优化。这题可以离线,如何充分利用离线的性质呢?注意到我们也可以把每个询问定位到O(\log n)个结点上。这样每个结点上就分别有一些直线和一些询问,结点之间相互独立,且直线总数和询问总数均为O(n \log n)级别。对于每个结点,我们发现如果把直线建成凸壳后,再把询问的x_0排序,那么它们对应的最小值所在直线的编号也是递增的。由于这样的单调性,我们就可以线性地回答询问了。时间复杂度O((n + q) \log n)