https://codeforces.com/contest/475/submission/360336341 怎么跑这么慢，难道说我写法某一块复杂度假了？ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 众所周知，ST 表解法很简单，但是 O(nlog⁡2V)O(n\log^2 V)O(nlog2V) 的复杂度还是太超模了，所以考虑换种解法。 考虑分治。 首先依旧势能分析，发现任意一个区间 [l,r][l,r][l,r] 的前缀和后缀 gcd⁡\gcdgcd 一定能分成 min⁡{r−l+1,⌊log⁡2V⌋}\min\{r-l+1,\lfloor\log_2 V\rfloor\}min{r−l+1,⌊log2 V⌋} 段，每段相同。 所以合并两个区间时，我们可以枚举这两个区间的每一段计算。每左右两段会对它们区间的 gcd⁡\gcdgcd 贡献两段长度之积。 先说结论，如果能 O(1)O(1)O(1) 求出 gcd⁡\gcdgcd，则这个解法是 O(nlog⁡V)O(n\log V)O(nlogV) 的。 证明：我们把这个递归树分一下层，会发现最下面 log⁡2log⁡2V\log_2\log_2 Vlog2 log2 V 层合并都是 O((r−l+1)2)O((r-l+1)^2)O((r−l+1)2) 的，所以下面那 log⁡2log⁡2V\log_2 \log_2 Vlog2 log2 V 层总的时间复杂度都是 O(nlog⁡V)O(n\log V)O(nlogV)。再看上面的，上面的每个节点大小都在 log⁡2V\log_2 Vlog2 V 以上，所以所有节点数不超过 2nlog⁡2V\frac{2n}{\log_2 V}log2 V2n ，每次合并是 O(log⁡2V)O(\log^2 V)O(log2V)，所以时间复杂度也是 O(nlog⁡V)O(n\log V)O(nlogV)。 现在的问题就是如何设计一个可以看做 O(1)O(1)O(1) 的求 gcd⁡\gcdgcd 的方法了。 注意到前面那篇题解提到： > 有人可能会说：诶你这计算 gcd⁡\gcdgcd 不算时间复杂度吗？其实势能分析一下，对于一个数 VVV 进行 nnn 次 gcd⁡\gcdgcd 运算，最多只会算 n+log⁡2Vn+\log_2 Vn+log2 V 次。所以次数可以忽略不计。 考虑充分运用这个性质。 * 对于上层节点，因为后面的前缀 gcd⁡\gcdgcd 一定是前面的因数，所以我们记录上一次合并的区间 gcd⁡\gcdgcd 直接用上，即可均摊 O(1)O(1)O(1)。 * 对于下层节点，由于节点数不超过 log⁡2V\log_2 Vlog2 V，所以我们直接 O(nlog⁡V)O(n\log V)O(nlogV) 预处理出每个点后 log⁡2V\log_2 Vlog2 V 个数的 gcd⁡\gcdgcd，合并时直接 O(1)O(1)O(1) 使用。 这样就能做到 O(nlog⁡V)O(n\log V)O(nlogV) 了吧，但为什么跑这么慢？

气死我了，给个 hack： 这两组数据会将“此用户已被标记为棕名”的代码卡到 O(n2)O(n^2)O(n2)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题意解析：给定一个长度为 nnn 的数组 AAA。qqq 次询问，每次询问给定一个数 vvv，求有多少 l≤rl\le rl≤r 满足 gcd⁡{Al,...,Ar}=v\gcd\{A_l,...,A_r\}=vgcd{Al ,...,Ar }=v。 首先因为一个区间的 gcd⁡\gcdgcd 一定是它子区间 gcd⁡\gcdgcd 的因数，所以势能分析一下，对于任意一个 lll，[l,n][l,n][l,n] 一定可以分成不超过 log⁡2V\log_2 Vlog2 V 段，每段内区间 gcd⁡\gcdgcd 值相同。 所以我们只需要求出所有段就可以得出所有答案了。 显然可以用 ST 表 O(nlog⁡nlog⁡V)O(n\log n\log V)O(nlognlogV) 实现。 有人可能会说：诶你这计算 gcd⁡\gcdgcd 不算时间复杂度吗？其实势能分析一下，对于一个数 VVV 进行 nnn 次 gcd⁡\gcdgcd 运算，最多只会算 n+log⁡2Vn+\log_2 Vn+log2 V 次。所以次数可以忽略不计。 Bonus：单点改，区间求。显然可以做到 O(qnlog⁡Vlog⁡log⁡V)O(q\sqrt{n\log V\log\log V})O(qnlogVloglogV )。