Codeforces 1732E. Location

JackF · 2022-10-26 14:42:48 · 题解

注意到 n,q 范围很小，考虑对序列分块。

设块长为 B，要对 \frac{n}{B} 个块维护每个块中 \frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)} 的最小值。

整块修改：当一个块内的 a_i 全部被赋值为 v，相当于需要快速找到 \frac{\operatorname{lcm}(v,b_i)}{\gcd(v,b_i)} 的最小值。先对于每个块都预处理出 mn_{d} 表示该块内最小的 b_i 满足 d\mid b_i。枚举 d=\gcd(v,b_i)，取最小的 \frac{mn_d\cdot v}{d^2} 即可。
上述做法在未知 b_i 的情况下无法确定 d 为 \gcd(v,b_i) 还是 \gcd(v,b_i) 的约数，但是把 \gcd 当作小的不会使得答案更小，因此不影响正确性。

散块暴力修改即可，查询平凡。

时间复杂度为 O(n\max d(V)+q(\frac{n}{B}\max d(V)+B\cdot \gcd))，d(V) 在 V=45360 时取到最大 100，实测 B=550 时跑得较快。

优化常数：

• 运用 基于值域预处理的快速 GCD 中的套路，可以 O(1) 求 \gcd。
• 运算乘法的时候最大是 50000^2，用 \text{unsigned int} 而不是 \text{long long}。