2016集训队论文集 吉如一《区间最值操作与历史最值问题》
1 hdu5306 Gorgeous Sequence
维护一个长度为$n$的序列，支持以下操作：
$0 l r t$：对于所有$i \in [l,r]$，将$a_i$修改为$\min \{ a_i,t\} $。
$1 l r$：查询区间$l,r$的最大元素的值。
$2 l r$：查询区间$l,r$元素的和。
多组数据，$\sum n, \sum m \le 10^6$。
做法
1）在线段树上维护区间内的最大值，最大值的个数，以及严格次大值。
2）递归到某个被修改区间完全包含的区间的时候，看这个区间的最大值、次大值和t的关系：
1.如果最大值小于等于t，那么直接返回。
2.如果严格次大值小于等于t，那么这次操作只会影响到区间内的最大值，打上标记之后返回。
3.否则，暴力递归左右子树。
复杂度
在论文中证明了是$O(m\log n)$。
代码
1 |
|
2 Picks loves segment tree
维护一个长度为$n$的序列$A$，支持以下操作：
$1 l r x$：对于所有$i\in [l,r]$，$A_i + = x$。
$2 l r x$：对于所有$i\in [l,r]$，$A_i = \min \{ A_i, x\} $。
$3 l r$：查询区间$[l,r]$内所有元素的和。
$n,m\le 3\times 10^5$
做法
因为有区间加减标记之后区间的最大值、次大值仍然可以维护，所以直接沿用上一道题的做法。
复杂度
“可以证明时间复杂度的上界是$O(m\log ^2 n)$，尽管在实际运行过程中表现得更像$O(m\log n)$。”
3 AcrossTheSky loves segment tree
维护一个长度为$n$的序列$A$，支持以下操作：
$1 l r x$：对于所有的$i\in [l,r]$，$A_i = \min \{ A_i,x\} $。
$2 l r x$：对于所有的$i\in [l,r]$，$A_i = \max\{ A_i,x\} $。
$3 l r$：询问$\sum_{i=l}^r A_i$。
做法
维护区间最大值、严格次大值、最小值、严格次小值，然后套用前面的做法。
复杂度
“可以沿用上一道题的证明，复杂度上界为$O(m\log n)$。”
将区间最值操作转化成区间加减操作
从上面几道题的做法我们可以发现，我们可以将区间取最值操作转化成对区间最值的加减，分别用两种标记维护对区间内的最值、非最值的修改。这样，我们把区间最值操作转化成了区间加减操作，在此基础上我们将可以维护与区间最值有关的、更加复杂的操作。
4 bzoj3064 CPU监控
维护一个长度为$n$的序列$A$，支持以下操作：
$1 l r x$：将区间$[l,r]$的数加上$x$。
$2 l r x$：将区间$[l,r]$的数变成$x$。
$3 l r$：询问$\min \{ A_i \mid i\in [l,r]\}$。
$4 l r$：询问$\min \{ B_i \mid i\in [l,r]\}$。
初始的时候$B_i = A_i$。每一次操作过后，我们都让$B_i = \max \{ B_i,A_i \}$。
$n,m\le 10^5,x\in [-10^9,10^9]$
做法
1）
如果对一个区间赋值后又进行了区间加，可以看做对这个区间进行了两次赋值操作。故而，我们可以将对某个区间的操作分成两个阶段，第一个阶段是区间加，第二个区间是区间赋值，对两个阶段分别维护操作标记的最小值，这样就可以维护区间的历史最小值了。
2）
其实可以直接将操作归为这样的一个形式：给定参数$a,b$，对于要修改的元素$x$，修改后$x’ = \min \{ x+a,b\}$。
合并两个操作$(a_1,b_1),(a_2,b_2)$：$(a_1+a_2,\min \{ b_1+a_2,b_2\})$。
然后考虑维护区间历史最小值，也可以用一个形式类似的标记$(a,b)$，表示对于一个操作前区间最小值为$x$的区间，操作后区间最小值是$\min \{ x+a,b\}$。假设之前进行过的操作的标记是$(a_1,b_1)$，之前进行过的操作的历史最小标记是$(a_2,b_2)$，现在合并过来的操作的历史最小标记是$(a_3,b_3)$，那么合并后得到的二元组是$(\min \{ a_2 ,a_1+a_3\} ,\min \{ b_2,b_3,b_1+a_3 \}$。
这个做法可以使用于所有的有区间赋值、加、取最值、查询历史最值，并且取最值操作和查询的历史最值类型相同（都是max或者都是min）的题目。
注意代码实现的时候不要把$\infty $设置得过于大，因为合并两个操作的标记的时候会直接累加，必须保证累加过后不会爆long long。
1 |
|
5 元旦老人与数列
维护一个长度为$n$的序列，支持以下操作：
$1 l r x$：对于所有$i\in [l,r]$，将$A_i$变成$A_i+x$。
$2 l r x$：对于所有$i\in [l,r]$，将$A_i$变成$\max \{ A_i,x\}$。
$3 l r$：查询区间$[l,r]$内元素的最小值。
$4 l r$，查询区间$[l,r]$内元素的历史最小值。
做法
沿用之前处理区间最值操作的那个思路，将操作分成对区间最小值的操作和对区间非最小值的操作。这样就变成了：对区间最小值加，对区间非最小值加，查询区间最小值，查询区间历史最小值。
可以分别对区间最小值和非最小值维护进行的操作，这些标记的和以及标记和的历史最大值。
注意在上传信息、下方标记的时候，儿子的区间最小值可能和父亲不一样。
下面这份代码中分别维护了对最小值和非最小值的标记，以及最小值和非最小值的历史最小值。实际上没有必要分别维护最小值和非最小值的历史最小值，因为我们在更新的时候也不会用到它们，直接记录整个区间的历史最小值就可以了。
1 |
|