【IOI2016】捷径

题意：有一条\(n\)个点的链，每个点又连接了一个特殊点，每条边有一个距离。现在你可以在链上某两个点间连一条权值为\(c\)的边使得得到的基环外向树直径最小。

考虑二分答案。

令\(len_i\)为链上点到最左端点的距离（即\(l\)的前缀和），

假设二分出的答案为\(k\)，那么要求存在一对点\(a,b\)，使得对于所有的\(len_j-len_i+d_j+d_i>k(i<j)\)，有\(|len_i-len_a|+|len_j-len_b|+d_i+d_j+c<=k\)。

绝对值不好处理，将绝对值分四种情况得到四个不等式，只要同时满足即可。

按照\(len_j+d_j\)的顺序枚举\(j\)，那么对应的\(i\)在按照\(len_i-d_i\)排序的数组内一定是一段区间，且端点单调。只需要满足\(i<j\)即可。将二分下界设为最大的两个\(d\)的和即可保证\(i<=j\)，再在查询的时候记录要求的值的次大值，如果最大值对应的位置正好是当前枚举的\(j\)那么用次大值更新答案。那么就能求出\(len_b+len_a\)以及\(len_b-len_a\)的范围。

于是枚举\(b\)，对应的\(a\)也是一段区间。不断更新区间端点即可，次数也是\(O(n)\)的。如果区间不为空则有解。