线段树四 Segment Tree Beats

我一直认为数据结构就是最优雅的暴力,虽说我实在认识到了这件事情之后才接触的这个东西,不过他也加深了我对这句话的理解
首先对于一个有条件的修改该如何处理?
当然我是第二次做类似的题,第一次是每次区间修改操作是如果区间内一个数的$x$的倍数那就除以$x$
做法就是开$1e5$颗平衡树还是多少颗我就记得不太清楚了,
第二次我遇到的操作是 区间$[l, r]$中 $A_i = min(A_i, x)$
对于这种操作反正我是不太熟悉, 但其实维护方法就很暴力(所以有一部分细节上的问题我可能会很久以后才会补充)
首先维护区间最大值, 次大值,和最大值出现的次数,次大值出现的次数
那样对于区间修改的操作我们就可以分成三类
1. x $\geq$ 区间最大值,那样就可已经return掉这个操作了
2. x $\geq$ 区间次大值 && x $\leq$ 区间最大值, 那样直接把最大值的贡献删掉,并且加上次大值的贡献,然后记录一下懒标记
3. x$\leq$ 区间次大值,那就递归下去修改就好
对于这个复杂度乍一看,$O(n^2)$的吧
但是实际上上面那两个分类保证了一件事
大致证明:区间内最有有$length$个不同的数, 首先经行前两个操作是喜闻乐见的,但要是进行第三个操作,每用一次那样区间不同的数量就会减少1,单次复杂度可能是$O(n)$的,有时候甚至能到$O(1)$
其实本质上,是什么拖累了时间复杂度呢?就是当区间中不同的元素特别多的时候,单次修改的时间复杂度会较为高昂,但是假设,我们修改了A个元素,那么就相当于区间的集合中少了A-1个元素,并且我们知道这次修改最大是Alogn的,那么下一次修改就相当于少了A-1个不同元素,也就是说,假设没有这次修改,下一次修改B个元素的话,那么有了这次修改下一次就相当于修改了B-A+1个元素,那么我们考虑将所有的修改操作的时间复杂度求和,接近于O(nlogn),但是,这并不完全,因为每次修改可能会导致某些区间的元素个数增加。那么我们考虑会增加多少呢?因为所有修改的元素都修改成了一个值,那么就相当于有些区间的元素的个数多了1。那么修改的时间复杂度就是期望上(Qlogn+nlogn),但是其实并不会跑满,而且实际效率很快。
上面这段话来自于这里

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注