算法学习笔记（14）：区间最值操作和历史最值问题

区间最值操作, 历史最值问题

来源

吉老师2016集训队论文， oiwiki， 网络上各种博客。

概述

区间最值操作指的是：

将所有的$i \in $ \((l, r)\)， \(a_i = min或max(a_i, k)\)。

历史最值问题指的是:

新定义一个数组 \(b[]\)， \(b[i] = max或min(b[i], a[i])\)。还有一种是历史版本和， 即\(b[i] = \sum a[i]\)。
再对 \(b[i]\) 进行一系列询问。
询问 \(\sum_l^r b_i\)， 或者 \(max_l^r b_i\)， \(min_l^r b_i\)

区间最值操作