yyy loves OI IV 题解

思路

令膜拜 yyy 的学生贡献 $+1$，膜拜 c01 的学生贡献 $-1$，并记前缀和为 $s_i$。区间 $(j,i]$ 中两类人数之差就是 $s_i-s_j$。

设 $dp_i$ 为划分前 $i$ 名学生所需的最少宿舍数。若最后一个宿舍对应 $(j,i]$，它合法的条件是 $|s_i-s_j|\le M$，或者该区间全部为同一种数字。

小规模可以枚举 $j$。当 $M\le10$ 时，记录每个前缀和值出现过的最小 $dp$，枚举 $s_i-M$ 到 $s_i+M$ 即可。满分范围需要维护前缀和值区间上的最小 $dp$，用线段树进行单点取最小和区间最小值查询。

做法

在线段树中先写入前缀 $s_0=0$ 对应的 $dp_0=0$。依次处理每个位置：

1. 在线段树上查询值域区间 $[s_i-M,s_i+M]$ 的最小 $dp_j$；
2. 维护当前同色连续段开始位置之前到 $i-1$ 的最小 $dp_j$，这正好覆盖“最后一段全部同色”的所有起点；
3. 两类转移的较小值加一得到 $dp_i$，再用它更新前缀和值 $s_i$ 的位置。

正确性证明

考虑任意最优划分的最后一个宿舍 $(j,i]$。若它不是纯色段，则合法性等价于 $|s_i-s_j|\le M$，第一类区间最小值转移一定枚举到 $j$。若它是纯色段，则 $j$ 位于当前同色连续段开始位置之前到 $i-1$ 的范围，第二类转移一定枚举到 $j$。因此算法不会漏掉任何合法的最后一段。

反过来，第一类转移选出的区间满足人数差限制，第二类转移选出的区间全部同色，所以每个转移产生的最后一个宿舍都合法。由 $dp_0=0$ 归纳可知，$dp_i$ 恰为前 $i$ 人的最少宿舍数，故输出 $dp_N$ 正确。

复杂度

线段树做法的时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。