Log Trick

Log Trick 是一种观察，可以通过发现具有一些性质的元素最多有 $\log n$ 个来降低复杂度。常见的例子有：

• 有单调性的区间按位操作，比如按位与/按位或。当区间扩大时，不同的结果值最多有 $\log U$ 个。
• 区间 $\gcd$。当区间扩大时，不同的结果值最多有 $\log U$ 个。

例子

例子：CF1632D - New Year Concert

给定一个长度为 $n$ 的数组 $a$，定义一次操作为修改任意一个数组中的元素。对于一个长度为 $k$ 的数组 $b$，定义 $f(b_1,b_2,\dots ,b_k)$ 为使得对于所有的 $1⩽l⩽r⩽k$，都有 $\gcd \{b_l,b_{l+1},\dots ,b_r\}\ne r-l+1$ 的最少操作次数。现在，请求出 $f(a_1),f(a_1,a_2),\dots ,f(a_1,a_2,\dots ,a_n)$ 的值。

数据范围：

• $1⩽n⩽2\times 10^5$。

• $1⩽a_i⩽10^9$。

对于每个点 $i$，我们用一个数组 $v$ 存放一些点对 $(pos,val)$，其中 $pos$ 表示满足 $\gcd (a_{pos},\cdots ,a_i)=val$ 的最大的下标 $pos$。由于 $val$ 之间至少相差 $2$ 倍，所以不同的 $val$ 至多有 ${\log }_2{a}_i$ 个，亦即 $v$ 最多有 ${\log }_2{a}_i$ 个元素。

我们从左到右遍历数组。对于每个元素，遍历 $v$ 数组并找出不符合题目要求的点，也就是说存在某个 $pos$ 到下一个 $po{s}^{\prime }$ 之间有点 $j$ 使得 $val$ 恰好等于 $i-j+1$ 的情况。每次遇到这种情况，我们就直接贪心地把 $a_i$ 改成一个和数组中的其他元素都不同的质数。并且题目不要求输出修改后的序列，所以实际上不需要修改，只需要把 $v$ 清空，只留下一个点对 $(i,1)$ 即可。

时间复杂度是 $O(n{\log }^{2}U)$，$U$ 是值域。有两个 $\log$ 的原因是计算 $\gcd$ 的复杂度也是 $\log U$。