【题解】[清华集训 2014] 玄学 线段树+二分 UOJ46 — Qiuly

• 题目链接
• 代码连接 1，代码链接 2

暴力做法即每次询问将 $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)$ 。