本文从WordPress迁移而来, 查看全部WordPress迁移文章
线段树
把一个转化变为一个线段
l->r,看做线段[l,r],用这个线段去覆盖总区间,这条线段的权值就是那个时间
先对所有操作即线段排序,按左端点升序排序
然后总区间每个单元的最小值Min初始化为INF,而1号单元初始化为0
在覆盖前先询问这个区间的最小值Min,如果最小值是INF,那么这次覆盖是不能进行的,这
说明之前都没有线段覆盖过这部分,这次也不能覆盖
找到最小值后,可以覆盖这个线段,本次产生的花费是c = Min + t,用这个c去更新区间[l,r]的每个单元
这个是原始的思想,这种思想的正确性,不难理解
但是问题是更新操作,得到c后,要更新整个区间的每个单元,这是会超时的,因为深入到每个叶子了
如果细想这个问题,可以知道,其实每次只需要更新每个区间的右端点即可
这个问题的正确性,不累述了,想想很容易明白的
数据比较大,一开始先排序去重离散化
注意无穷大的设置,设置为0x3f3f3f3f会wa!要设置一个更大的值
1 |
|