题解：P2418 yyy loves OI IV

_std_O2 · 2025-09-21 12:13:17 · 题解

记 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 就行了。

所以代码自己写。