天爱星马剃

· · 题解

给一个大常数垃圾做法。

我们先把原序列的每个数质因子分解之后对指数是奇数的质因子保留一个，这样得到新序列 \{a'_n\}，有性质满足当 a'_i=a'_j 时 a_i \cdot a_j 是完全平方数。这个时候我们的限制就是要求每一段的 a'_i 都互不相同。也就是说把一段数修正为合法的花费次数是每种数都只保留一个，即总数减去种类数。我们记 l_i 表示上一个恰好等于 a'_i 的位置。

考虑 dp。设状态 f_{i,j} 表示把前 i 个数分段，更改了 j 个位置，最小划分段数。转移考虑以 i 结尾的区间的左端点。如果我们把 j \in [1,i] 里所有的 l_j 都标记为 1，那么把 [p,i] 划分为一段的代价就是区间 [p,i] 的和。显然这个区间和不能超过 k，不然没有状态可供转移。那么我们只需要枚举最后 k 个 1，设当前枚举的 1 的位置在 p，它后继的 1 在 q，且 p 是倒数 w 个 1。那么有转移：

f_{i,j+w-1} \gets \min_{p \le a < q} f_{a,j} + 1.

这样的转移每次 O(k)，枚举 k 个位置转移，取 \min 开 k 棵线段树维护，时间复杂度 O(k^2\log n)，枚举 1 的位置可以用链表或者 set。总时间复杂度 O(nk^2\log n)，倒闭。但是我们注意到这个每次插入 l_i 为 1 的时候，对于 1 之间的先后关系改变只有 O(1) 个，也就是说这个取 \min 很多位置的结果不变，只会改变 l_i 的前驱和其自身。所以我们提前保存取 \min 的结果即可，这样转移复杂度 O(k^2)，每次插入 l_i 的复杂度 O(k \log n)，总复杂度 O(nk^2+nk\log n)。线段树不要写的太劣就可以轻松跑过。

Accepted submission.