题解 UVA1392 【DNA Regions】

2019-08-27 14:26:39


数据结构学傻了.jpg

如果一个区间 $[L,R]$ 满足条件,那么

$$\begin{aligned}\frac{sum_R-sum_{L-1}}{R-L+1}&\leq p\%\\sum_R-sum_{L-1}&\leq p\%(R-L+1)\\sum_R-sum_{L-1}&\leq p\%R-p\%(L-1)\\sum_R-p\%R&\leq sum_{L-1}-p\%(L-1)\end{aligned}$$

这里的 $sum_i$ 表示 $[1,i]$ 中有多少个不相等的。

那么可以考虑枚举右端点,于是只要找到一个最小的满足 $sum_{L}-p\%L\geq sum_R-p\%R$ 的 $L$ 就好了。

考虑使用权值线段树。假设我们已经把所有的 $sum_i-p\%i$ 离散化了,离散化后的数组是 $a$ 。

假设当前扫到了 $i$ 。我们只需要查询 $[a_i,n]$ 范围内的最小值即可得到最小的满足条件的 $i$ ;然后我们再把 $a_i$ 位置修改为 $i$ 。

也就是说,这个权值线段树需要资瓷单点修改、区间取 $\min$ 。

注意离散化的时候要加个 $0$ 进去( $L-1$ 可能等于 $0$ ),然后一开始要把 $a_0$ 设成 $0$ 。

具体实现及细节见代码