题解 P4758 【[CERC2014]Mountainous landscape】

JoshAlMan · 2021-01-26 23:09:50 · 题解

如果给我们一个区间 [l, r]，我们要看这里面的点有没有可能作为答案，即 [l, r+1] 区间有没有折线有部分在该线上方，这个很容易做，可以在预处理这一段的上凸包（越靠上越好，那么被完全包含在内测的凸包的确是没有用的）后 O(\log n) 得出，即二分出斜率大于当前线斜率的第一个折线右端查是否在这个线上方即可（还有一些细节，如没有大于的就是第一个点）。

因此我们可以建一棵线段树，每个节点预处理一个上凸包。

对于每个点，在线段树上二分即可。时间复杂度 O(n \log^2 n)，空间复杂度 O(n \log n)。