IOI2016 shortcut 题解

zzzYheng · 2024-02-20 20:34:26 · 题解

题意：

现在有一条链，点编号 1\sim n，i 和 i+1 之间边的边权为 l_i。

点 i 的下面还挂了一个儿子，与儿子边的长度为 d_i（0 表示没有）。

你可以选择两个点 s,t\in [1,n]，在它们间连一条长度为 c 的边。

你的目标是最小化添加边后这张图的直径。

数据范围：n\le 10^6,1\le l_1\le 10^9,0\le d_i \le 10^9,1 \le c_i \le 10^9。

思路：

首先我们假设 i 号点距离 1 号点的距离为 p_i.

最小化两点间距离的最大值，容易想到二分答案，假设现在判定直径能否小于 lim.

显然距离最远的点一定是两个下挂叶子，假设它们的父亲分别是 x 和 y（x <y），它们只有两种走法：直接走过去、走新加的边再过去。长度不能都大于 lim，对应了以下两个式子：

对于下面这个式子，绝对值肯定是要拆的，但是分类讨论的方法肯定不行，因为 s 和 t 的位置并没有确定。但是可以考虑把 |a-b| 拆成 \max(a-b,b-a)，而 \max>lim 就等价于存在一个大于 lim。

所以下式等价于下面四个式子之一成立：

整理一下，把和 x,y 有关的放到一边，和 s,t 有关的放到一边：

所以限制就是 d_x+d_y+p_y-p_x>lim 和上面四个式子之一不能同时成立。

即 d_x+d_y+p_y-p_x>lim 满足时，上四式都不能成立，也就是下四式全部满足：

容易发现不同 (x,y) 对应的限制是可以合并的。对于所有满足 d_x+d_y+p_y-p_x>lim 的 x<y 对，统计上面四个式子每个的 \min 即可，显然这是一个二维偏序问题。这样所有限制就合并成了两个对 p_s\pm p_t 的范围限制。

对于这两个范围限制，假设为 p_s+p_t\in [l_1,r_1] 和 p_s-p_t\in [l_2,r_2]。枚举 s 的位置，利用双指针可以求出两个限制分别对应的对 t 取值的一个区间限制，简单判一下这两个区间是否有交即可。

复杂度瓶颈在于每次二分都要做一次二维偏序，复杂度为 \Theta(n\log^2n)，无法通过。

考虑继续优化，对于多维偏序问题我们第一个要考虑的优化就是是否某一维偏序限制是无效的。

我们尝试去除 x<y 这一维偏序。这样会多出一些满足 x\ge y 且 d_x+d_y+p_y-p_x>lim 的对的贡献。

这时第二个式子的含义也就变成了 d_x 加上 d_y 减去 x 和 y 之间的距离，发现如果这个值 >lim，那 d_x+d_y 就也会 >lim，那无论怎么连边，一定无解。所以我们将二分下界设为 \max d_x+d_y，就可以避免出现这种贡献。

但我们还是不能直接做一维偏序，因为就是 x=y 的情况我们还是可能多算贡献，解决方法是记录一个次小值，当最小值冲突时我们用次小值即可。

我们提前排序，每次做一维偏序的复杂度就是 \Theta(n)，这样总复杂度就是 \Theta(n\log n)。

总结：

对于这种题目，最重要的就是要把条件和限制都清晰地列出来，然后一步一步地推即可。

这题一个比较重要的 \text{trick} 就是 |a-b| 不仅可以通过分类讨论拆，也可以直接拆为 \max(a-b,b-a)。

还有就是优化多维偏序一定要先考虑是否有偏序限制是无效的。