本文从WordPress迁移而来, 查看全部WordPress迁移文章
堆 线段树
原解是堆,32个大堆,32个小堆,每个点都要插进去大堆小堆里面
线段树解法
东爷威武,东爷曾说,“这个题目嘛,说白了,就是要维护最大值,最小值就可以了
所以任何一个数据结构能做到这点都行,例如平衡树啊什么的。”
所以就试一下线段树吧,因为线段树也是可以维护最大值,最小值的
我们这样设置线段树,把所有点放在一排,当做一个区间
因为最多60000个操作,就当做60000个操作都是添加点,那么最多60000个点
所以我们线段树的总区间长度是60000,每个单元是一个点的信息
一开始一个点都没有,所以总区间内每个单元都没有信息。
没添加一个点,就是更新对应单元的信息,删除也是一种更新,也是更新对应单元的信息
对于一个线段的节点记录的信息如下
1 | struct SegTree{ |
对已K维,一个点最多可以分出2^K的情况,所以每种情况都要记录最大最小值,所以维护最大,最小值,要维护2^K种情况
Max[M],Min[M]就能维护所有情况,M为32,因为最大2^5 = 32
然后线段树中最常见的就是PushUp和PushDown操作,自底向上,自顶向下,两种更新
每修改一个点(单点修改),就从叶子开始将信息传上去
而查询操作,就是总区间查询,查询复杂度是O(2^K),可以认为是常数级的因为2^K这个东西很小
查询的就是总区间的最大值,最小值(即现在存在的所有点的最大,最小值),但注意,查询按照2^K种总类来分别查询
1 |
|