自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 22:52:41，当前版本为作者最后更新于2023-12-29 11:30:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[EC Final 2021] Vision Test

设 $K = \frac{a}{c},B = \frac{b}{c}$，则题目需要找到 $K,B$ 使得满足 $a_i = \lfloor{Ki+B}\rfloor$.

如果固定 $K$，考虑 $B$ 需要满足的条件：

则如果 $\min(a_i+1-Ki)>\max(a_i-Ki)$，那取 $B = \max(a_i-Ki)$ 就得到了一组解。

如果不满足的话，也就是此时 $\min(a_i+1-Ki)-\max(a_i-Ki)\le 0$。

设 $i_{\min}$ 为取到 $\min(a_i+1-Ki)$ 的下标 $i$，$i_{\max}$ 为取到 $\max(a_i-Ki)$ 的下标 $i$。

则如果 $i_{\min} > i_{\max}$，增大 $K$ 会使 $a_{i_{\min}}+1-Ki_{\min}-(a_{i_{\max}}-Ki_{\max})$ 减小，从而不可能成立，因此此时要减小 $K$。同理，若 $i_{\min}<i_{\max}$ 则要增大 $K$。

不难发现 $K$ 满足可二分性。于是在 Stern-Brocot Tree 上二分 $K$，这同时能满足题目中字典序的要求。

由于 $K$ 在 Stern-Brocot Tree 中的深度很大，二分时要每次跳一条链才能保证复杂度。每次在链上二分求出能跳的长度，总共 $O(\log^2 V)$ 次调用 check。实际上使用倍增二分，只有 $O(\log V)$ 次调用 check，因为 check $O(t)$ 次后值域会变为原来的 $2^t$ 级别。

接下来问题是对于一个区间，给定 $K$，查询 $\max(a_i-Ki)$ 及其下标，$\min$ 的问题同理。

可以直接用回滚莫队（不删除莫队）制作出区间凸包信息，然后在凸包上二分查询，时间复杂度 $O(n\sqrt q + q\log V \log n)$。

当然也有多种 polylog 做法，比如对序列进行分治，每次处理跨过 $mid$ 的询问，需要处理出 $[ql,mid],[mid,qr]$ 两个前缀凸包的信息。

建前缀凸包的过程是加入一个点，弹出栈中的若干个点。那可以看作当前点向弹栈后下一个点连边，形成一棵树，前缀凸包信息就是一条当前点到根的链，查询时在树链上倍增即可替代凸包上二分。时间复杂度 $O(n\log^2 n + q\log V\log n)$。

Code