本文从WordPress迁移而来, 查看全部WordPress迁移文章
线段树
题意:给出一段不下降序列,只有询问没有修改,每次询问一段区间内,连续的数字最大个数是多少(是个数,好像1 1 1 1,重复了4次,次数又最大,那么输出4)
比较简单的线段树,用分治的思想去解决
一个线段树需要记录的信息有
1 | struct SegTree{ |
建树时,通过一个自底向上的更新,将左右孩子的信息汇聚到当前区间里,为了函数可以重用,代码不写PushUp,改写为Del,因为这个函数在查询时还需要用到。
自底向上的更新是
- 当前区间的前缀和后缀,分别是左孩子的前缀和右孩子的后缀
- 当前区间的前缀和等于左孩子的前缀和,如果左孩子的前缀和等于左孩子区间长度(即整个区间都是这个数字),并且右孩子的前缀和左孩子的前缀相同,那么当前区间的前缀还可以延伸到右孩子区间去;rt.presum = lson.presum + rson.presum
- 同理,对于后缀和也是这样的,要么等于右孩子的后缀和,如果右孩子的后缀能延伸到左孩子的后缀,那么rt.sufsum = rson.sufsum + lson.sufsum
- 当前区间的最大重复次数,要么等于左孩子的最大重复次数,要么等于右孩子的最大重复次数,要么左孩子的后缀 = 右孩子前缀,可以将左孩子后缀和 + 右孩子前缀和
对于查询操作,和build tree的道理是一样的,都是分治
1 |
|