CF 2500 贪心

I. Square-free division (hard version)

考虑 dp，设 \(f_{i,j}\) 表示考虑了前 \(i\) 个数，修改了 \(j\) 个分割的最小数量的子段。枚举上一个子段的结尾 \(k\)，并设 \(val(i,j)\) 表示 \([i,j]\) 这一段最少修改多少个数使得其变成合法子段，那么一个 \(O(n^2)\) 的 dp 式子就出来了，\(f_{i,j}\leftarrow \min\{f_{k,j-val(k+1,i)}+1\}\)。

注意到 \(k\le 20\)，所以可以枚举 \(val(k+1,i)\) 的取值 \(m\)，我们只需要找到一个下标 \(k\) 使得 \(f_{k,j-m}\) 最小，不妨设 \(g_{i,j}\) 表示一个最长的后缀 \([g_{i,j},i]\) 使得修改恰好 \(j\) 个数能成为合法子串。那么 \(k\) 这个决策点的取值应为 \(g_{i,m}\)。

为什么 \(k\) 取最小就是最优呢，注意到 \(f\) 是单调不降的，所以越往左的 \(k\) 对应的 dp 值就越小。

\(g_{i,j}\) 的求法考虑双指针，即 \(j\) 固定的情况，\(g_{i,j}\) 是随着 \(i\) 的增加而增加的。我们把每个 \(a_i\) 的平方因子扔掉，那么两个数乘积为完全平方数这一条件就可以化成两个数是否相等。

复杂度 \(O(nk^2)\)。有高妙的 \(O(nk+a_i)\) 做法但是我不会。

code。

II. Ivan and Burgers

猫树分治。对于区间 \([l,r]\) 预处理后缀 \([i,mid]\) 和前缀 \([mid,j]\) 的答案，对于跨越 \(mid\) 的询问可以快速合并，不跨越 \(mid\) 的向两边递归。

注意这个复杂度不是三只老哥而是两只，因为每次只会遍历在当前 \([l,r]\) 区间内询问的贡献，每次询问只会遍历一次，所以复杂度 \(O(n\log n\log V+q\log^2 V)\) 的。

code。

III. Complete the MST

结论是只会更改一条边的权值，其余边权设置为 \(0\)。