题解：P15130 [ROIR 2026] 超级跳跃

Register_int · 2026-03-21 18:24:53 · 题解

爆标做法。

答案就是 [l,r] 内的点构成的凸包点数。这个部分分已经把分治写脸上了，那么分治的每一层我们要干这两个事情：

• 存下 mid 左右两侧的前缀凸包。
• 对两个凸包进行合并。

首先可以持久化李超树做到 \mathcal{O}(n\log^3 n)，但是太不牛了。发现凸包其实是一个单调栈的结构，在跑单调栈时，将末尾元素向上一个元素连边，会形成一棵树。那么一个凸包可以表示为一条到根链。倍增找切点即可，时间复杂度 \mathcal{O}((n+q)\log^2 n)。

能不能再给力一点？仿照 这个题 的方法，进行树剖，那么一个凸包可以表示为 \mathcal{O}(\log n) 段连续的数组的拼接。那么先用双指针定位，再二分即可。时间复杂度 \mathcal{O}((n+q)\log n)。