[EC Final 2021] Vision Test

· · 题解

[EC Final 2021] Vision Test

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

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

a_i \le Ki+B < a_i+1 \max(a_i-Ki) \le B < \min(a_i+1-Ki)

则如果 \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