题解

思路

设 $dp_i$ 为前 $i$ 个元素的合法划分数，$dp_0=1$。若子段 $(j,i]$ 中恰好出现一次的值不超过 $k$，则 $dp_j$ 可以转移到 $dp_i$。

做法

子任务 1：枚举切分

枚举 $n-1$ 个间隙是否切开，逐段统计频率并验证。复杂度 $O(2^n n^2)$。

子任务 2：二次动态规划

固定右端点 $i$，从 $i$ 向左移动左端点，维护每个值的出现次数和恰好出现一次的值数，即可在 $O(n)$ 内求出 $dp_i$。总复杂度 $O(n^2)$。

子任务 3：分块优化

扫描右端点 $i$。对每个候选切点 $j$，维护 $c_j$，表示 $(j,i]$ 中恰好出现一次的值数，同时在位置 $j$ 存放权值 $dp_j$。需要查询所有 $c_j\le k$ 的权值和。

设 $a_i$ 上一次、上上次出现位置为 $p_1,p_2$。加入 $a_i$ 后：

• $j\in[p_2,p_1-1]$ 时，出现次数由一变二，$c_j$ 减一；
• $j\in[p_1,i-1]$ 时，出现次数由零变一，$c_j$ 加一。

于是每步只有两次区间加减一、一次全局查询和一次插入。

对切点分块。每块维护懒标记、按块内原始 $c$ 值分桶的 $dp$ 权值和，以及当前 $c\le k$ 的权值和。整块加减一只移动一次阈值；散块修改先下放标记，再用 $O(B)$ 重建。取块长 $B\approx\sqrt n$，单步复杂度为 $O(B+n/B)$。

复杂度

满分算法时间复杂度 $O(n\sqrt n)$，空间复杂度 $O(n\sqrt n)$；实际分桶总容量为块数乘 $O(n)$。