暴力做法即每次询问将 $a_k$ 从左到右对于所有的修改都做一遍更新。

考虑如何将修改合并。

对于一个修改,其对应区间为 $[l,r]$,那么原序列最多会被分割成 $3$ 个区间,即:$[1,l-1],[l,r],[r+1,n]$ 。同一区间内的元素收到该修改的影响是一样的。显然这个时候再加入一个修改,原序列最多会多产生 $2$ 个区间,也就是说,$k$ 个修改一共最多将原序列分割成 $2k+1$ 个区间。

因为同一区间内所受到这 $k$ 个修改的影响是一样的,因此可以直接维护区间,查询的时候二分找对应区间即可。

考虑对修改建线段树,合并左右子树的时候复杂度显然是和” 原序列被分割的段数” 有关的,即跟区间长度有关,线性复杂度。强制在线的话,依旧考虑线段树,当一个节点所管辖的 $[l,r]$ 修改全部被执行过后,就求出这个节点的信息(即从左右儿子合并),然后标记一下。显然一个节点最多就只需要求一次信息,因此复杂度依旧是 $O(n\log n)$。查询复杂度为 $O(q\log n)$ 。

分类: 文章

Qiuly

QAQ

2 条评论

Walking_Dead · 2020年11月20日 9:31 下午

这个实际上就是二进制分组吧

回复 Qiuly 取消回复

Avatar placeholder

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