CF671C Ultimate Weirdness of an Array

区间 max gcd 计数显然没有任何性质，考虑倒序枚举，转化为计算 \(\sum_i\sum_{l,r}[f(l,r)\ge i]\)。

考虑用一个线段树维护这个东西。\(x\) 节点上存最小的满足 \(f(x,r)<i\) 的 \(r\)。那么一次操作只需要全局求和。

我们考虑 \(i+1\to i\) 的过程，显然只有 \(i\) 的倍数会对这些位置产生影响，假设下标序列为 \(p_{1\sim m}\)。

• \(m = 1\)：显然不用管。
• \(m=2\)：我们分几个位置讨论：
• • \([1,p_1]\)：这些位置最右端要到 \(p_{m-1}-1\)，取多就取不到 \(i\) 了，所以和 \(p_{m-1}\) CheckMax。
  • \([p_1+1,p_2]\)：这些位置能取到 \(p_m-1\)，所以和 \(p_m\) CheckMax。
  • \([p_2+1,n]\)：咋取都行，和 \(n+1\) CheckMax。

注意到线段树维护的序列单调不降，所以直接线段树二分+区间 assign 即可。时间复杂度 \(\mathcal O(nd(n)+w\log n)\)。