487b专题

CodeForces 487B Strip

题意: n(10^5)个人分组  每组最少L个人  每组的差异为组中人最大价值-最小价值  要求差异均不超过S  问最少分几组 思路: 假设已经知道组的区间[l,r]那么计算差异就是简单的rmq问题  可以用线段树搞 我们可以用dp[i]表示到i位置产生的最少组数 假设从i位置开始分一组  会影响到哪些dp呢  我们可以利用二分+rmq找到这个组最远延伸到哪里  从L到最远点这个区间的d