隐藏
线段树区间取最值与历史最值问题梳理与例题选讲 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

线段树区间取最值与历史最值问题梳理与例题选讲

jiry_2大佬的研究下,线段树有了全新一类的应用,也使得线段树从NOIP难度上升了许多。无法使用懒标记的区间取最值问题与难以分析的历史最值问题成为了线段树全新的难点。

区间取最值问题

按照jiry_2论文上的讲题顺序介绍例题:

例1.Gorgeous Sequence

题面

    维护一个数组$a$,支持以下操作:

  • 给出$l,r,x$,对$i\in[l,r]$,将$a_i$变为$\min(a_i,x)$。
  • 给出$l,r$,对$i\in[l,r]$,询问$a_i$的最大值。
  • 给出$l,r$,询问$\sum_{i=l}^r a_i$。

题解

线段树维护最大值$max$,次大值$sec$,最大值个数$maxt$。
若使区间$[L,R]$对$x$取$\min$,先定位这个区间,对定位到的区间暴力递归:

  • 当$max\le x$,直接退出。
  • 当$sec\lt x\lt max$时,维护区间和,更新$max$,打标记,退出。
  • 当$sec\ge x$,递归左右儿子。

时间复杂度证明

原论文给出了一种正确的证明,这里用另一种方式证明。

我们只讨论含有递归的修改操作,若不递归,说明满足$sec\lt v\lt max$或$v\ge max$,这对时间复杂度没有影响。

若递归,此时必有一个$max$被修改到$\le$原有$sec$,至少把一个数变成和另一个数一样,即可用值域至少减少了$1$,值域只可能减少$n$次,而在线段树上定位的时间复杂度是$O(\log n)$,故修改操作的时间复杂度是$O(n\log n)$,故总时间复杂度是$O(n\log n+q\log n)$。

例2.Picks loves segment tree

题面

    维护一个数组$a$,支持以下操作:

  • 给出$l,r,x$,对$i\in[l,r]$,将$a_i$变为$\min(a_i,x)$。
  • 给出$l,r,x$,对$i\in[l,r]$,将$a_i$变为$a_i+x$。
  • 给出$l,r$,对$i\in[l,r]$,询问$a_i$的最大值。
  • 给出$l,r$,询问$\sum_{i=l}^r a_i$。

题解

不难发现即使有区间加减,例1的信息还是可以维护,因此直接套用例1做法。

时间复杂度证明

感性认识:有了区间加减操作,可选值域肯定会增加,因此时间复杂度会比$O(n\log n)$要大。

不会证明(例1的证明不能沿用),jiry_2说时间复杂度是$O(n\log^2n)$的(如果能看懂的可以看jiry_2的论文)。

例3.AcrossTheSky loves segment tree

题面

    维护一个数组$a$,支持以下操作:

  • 给出$l,r,x$,对$i\in[l,r]$,将$a_i$变为$\min(a_i,x)$。
  • 给出$l,r,x$,对$i\in[l,r]$,将$a_i$变为$\max(a_i,x)$。
  • 给出$l,r$,询问$\sum_{i=l}^r a_i$。

题解

我们只需要维护区间最小值,区间严格次小值,区间最小值个数,区间最大值,区间严格次大值,区间最大值个数,就可以套用例1的方法做了。

时间复杂度证明

不难发现仅有这两个操作,值域还是只会减少不会增加,故时间复杂度和例1一样是$O(n\log n+q\log n)$的。

一类通用的转化

我们发现通过例1的思想,区间取最值操作可以一直递归到某个区间然后修改最大值,这就是只对最大值有影响的区间加减问题。
因此对于含有区间取最值的线段树问题,我们可以将维护的信息分为最大值的信息与非最大值的信息分开维护,区间取最值操作一直递归到$sec\lt x\lt max$退出,而其他的操作定位了区间后就可以退出了。

这样我们就使用了一个$\log$的代价将区间取最值转化为了区间加减问题。
这样转化过后,套入了其他操作的区间取最值问题思路就很清晰了。

其他例题

可以参考jiry_2的论文,讲得很清楚。

历史最值问题

考虑一类问题,除了维护最新的信息,还要查询历史的最大值/最小值/求和信息,这类问题我们可以使用懒标记进行维护。

例7.CPU监控

题面

    维护一个数列$a$,支持区间加减,区间覆盖,询问一段连续区间的最大值与历史最大值。

题解

传送门

总结

这道题我们用到了一个技巧,将两种操作转化成了一种通用的标记,但是这个标记包含区间取最值的操作,因为这道题标记的$\max$和历史查询的$\max$是同向的故可以采用这样的标记合并从而绕开区间取最值的操作。
同时我们还发现,历史最值的标记和当前的标记很类似,只是合并标记的时候略有不同,一般定义了标记的加法与大小关系后,历史标记的合并过程都是一样的。

例8.V

题面

    区间加,区间变成$\max\lbrace a_i-v,0\rbrace$,区间覆盖,询问单点的最大值和历史最大值。

题解

传送门

总结

和上题类似的,标记可以合并,信息处理就很方便了。

例10.元旦老人与数列

题面

    最开始xyz111有两个长度为$n$的完全相同的数列$A$和$B$,接下来有$m$次操作,每一次操作都是以下的四种之一:
    1.对于所有的$i\in[l,r]$,将$A_i$变成$A_i+c$。
    2.对于所有的$i\in[l,r]$,将$A_i$变成$\max(A_i,d)$。
    3.对于所有的$i\in[l,r]$,询问$A_i$的最小值。
    4.对于所有的$i\in[l,r]$,询问$B_i$的最小值。
    在每一次操作结束之后,xyz111 都会进行一次更新:对于所有的$i\in[1,n]$,将$B_i$变成 $\min(B_i,A_i)$。

题解

传送门

总结

这道题和前两题不同在于,前两题的标记可合并,而本题的标记最值方向与历史最值方向相反,写出的标记表达式无法合并,故不能套用上面的方法。
为了解决这个问题,我们使用区间取最值时的转化方法,将所有的操作分为最小值与非最小值进行考虑与维护,故问题得到解决。

姥爷们赏瓶冰阔落吧~