CLICK HERE(LINK)

$\large\text{Outline}$

• 挺有意思的题目。

$\large\text{Algorithm}$

• 同时存在删除元素和单点增加，计算最小代价，单看操作本身找不到突破口。
• 此题的特殊之处在于值域范围 $[1,10^6]$，那么显然支持直接枚举 $\gcd$ 的素因子。
• 考虑已知 $\gcd$ 包含的素因子（设为 $g$），计算当前代价：对于区间 $[(k-1)\cdot g+1,k\cdot g]\,(k\in[1,\lceil\frac{maxval}{g}\rceil])$ 中的数，显然存在分解 $b$ 使得 $[(k-1)\cdot g+1,(k-1)\cdot g+b+1]$ 中所有数被删除更优，其余数增加到 $k\cdot g$ 更优。
• 由于 $b$ 只与 $g$ 有关，可以在枚举 $g$ 时直接二分，对于 $k$，依然可以暴力枚举（这一步是埃筛的复杂度 $O(n\log\log n)$）。
• 得到区间内数的个数等信息，直接在读入时前缀和即可。

$\large\text{Notes}$

• 静态区间查询没有必要用树状数组！！！