自动搬运

查看原文

来自洛谷，原作者为

	JoshAlMan i人

搬运于2025-08-24 22:03:18，当前版本为作者最后更新于2021-01-26 23:09:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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