题解：P2418 yyy loves OI IV

记 $sum_i$ 为 $[1,i]$ 中 膜拜 yyy 和 c01 的人数的差。

记 $f_i$ 为 考虑到第 $i$ 个人时所需最少的宿舍数量。

易得 $O(n^2)$ 递推式为 $f_i=\min\limits_{\lvert sum_i-sum_{j-1} \rvert \le m~\vee~sum_i-sum_{j-1}=i-j+1} f_j+1$。

现在考虑优化，首先注意到条件 $\lvert sum_i-sum_{j-1} \rvert \le m$，容易想到这是两个在数轴上的点的距离小于等于 $m$（初一知识）。

这时如果我们想有没有一种数据结构能统计数轴上 $j\in[x-m,x+m]$ 的 $\max f_j$，就容易想到值域线段树了。

所以我们只需在 $sum_i$ 点进行单点修改，然后区间查询 $[sum_i-m,sum_i+m]$ 中的最大值然后更新 dp 就行了。