在线静态区间 gcd

· · 算法·理论

若使用辗转相除，则显然有一个 \Omega(n+q+\min(n,q)\log V) 的下界。现在说明这个下界可以达到。

1. $q>n

建区间分治的结构。对于跨过中点的询问，先求出左区间后缀和右区间前缀的 \gcd 分段结构。预处理这 O(\log^2 V) 对数的 \gcd，显然复杂度也是 O(\log^2 V)，那么找到左右端点对应的分段即可。区间长度 \le \log V 时停止递归直接 O(\log^2 V) 暴力即可。时间复杂度 O(n(\log n+\log V))。

这无法解决 \log V=o(\log n) 的情形。

考虑消除掉上面的 O(n\log n)。这来源于在分治的结构上找分段和 O(1) 求前驱后继。

前者实际上可以直接扫描线扫左端点和右端点，对每个左端点和右端点把分段存下来。后者可以直接压位。

时间复杂度 O(n\log V+q)。

  1. q\le n

块长为 \Theta(\log V) 分块。整块对应序列长度为 O(n/\log V) 的问题，可以直接扫右端点并且记录分段。散块直接暴力。这样每次询问只需要求 O(\log V) 个数的 \gcd。

时间复杂度 O(n+q\log V)。

当然，允许离线的话，存在更加简单的做法。不过有一个遗留问题：可以发现 part1 的分治结构需要耗费 O(n\log V) 的空间。这个能优化吗？