python/TangDou/AcWing/SegmentTree/Gorgeous/区间最值操作与区间历史最值详解.md

## [区间最值操作与区间历史最值详解](https://www.luogu.com.cn/blog/Hakurei-Reimu/seg-beats)

本文讲解了一种叫做 $Segment$ $Tree$ $Beats$ 的使用线段树维护区间最值操作的方法，和维护区间历史最值的常用手段。主要参考了了吉老师 $2016$ 年集训队论文（见文末参考资料）。

前置知识：**懒标记线段树**。

### 区间最值操作
首先假设我们有一个序列 $A$。区间最值操作是指，给定 $l,r,k$，对于所有 $i\in[l,r]$ ，将 $A_i$变成 $\min(A_i,k)$ 或 $\max(A_i,k)$ 的一种操作。下面由一道例题引入。

[$HDU5306$. $Gorgeous$ $Sequence$](http://acm.hdu.edu.cn/showproblem.php?pid=5306)

> 给出一个长度为 $n(n\leq 10^6)$ 的序列 $A$ 和 $m(m\leq 10^6)$ 次操作，每次操作为以下三种类型之一：
> $1$. 给出 $l,r,k$，对于所有 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,k)$
> $2$. 给出 $l,r$，求序列 $A$ 区间 $[l,r]$的 **最大值**
> $3$. 给出 $l,r$，求 $\displaystyle \sum_{i=l}^{r}$​

在这道题中，第一种操作就是 **区间最值操作**。我们发现，关于区间 **最大值的询问** 是可以使用 **带懒标记的线段树维护** 的，而 **区间和则不是很容易求出**，因为这 **不能在下传标记时快速更新答案**。

考虑到区间取 $\min$ 的操作只会对 **最大值超过 $k$ 的节点产生影响**，我们可以在这方面产生思路。为了使复杂度变低，线段树的一个节点要维护三个信息：
- 区间最大值 $mx$
- 区间严格次大值 $se$ 
- 最大值的个数 $cnt$

那么，一次区间 **最值操作$min$** 作用在这个节点上时，可以被分为以下三种情况：

- $k≥mx$，此时该操作不会对当前节点产生影响，直接退出
- $se<k<mx$，此时这个节点维护的区间中所有最大值都会被修改为 $k$，而最大值个数不变。将区间和加上 $cnt\cdot(k-mx)$ ，打上懒标记，然后退出即可
- $k\leq se$，此时无法快速更新区间信息，因此我们 **需要继续递归到左右子树中**，回溯时合并信息

举个例子，现在要以 $k=2$ 对下面这棵线段树维护的区间取 $\min$。每个节点左侧表示区间最大值，右侧表示严格次大值。
<center><img src='https://cdn.luogu.com.cn/upload/image_hosting/2b77ype7.png'></center>

按照上面描述的操作，我们应该沿着红色的边 $dfs$，最后 **在红色的节点上更新区间和并打上标记**。

这样做的复杂度可以证明是 $O(mlogn)$ 的。


### 支持区间加减
我们在支持上一道例题中所有操作的同时，加入区间加操作。

此时有两种考虑这个问题的方法：

- 套用上一题的做法，我们只需把标记换成二元组 $(add,v)$，表示将当前节点维护的区间先加上 $add$ 再与 $v$ 取最小值。**合并标记** 时，先考虑给当前节点加上一个标记，我们除了更新当前节点的区间加标记 $add$，还需要把它加到 $v$ 上；而给当前节点取最小值可以直接将标记对它取 $\min$。形式地说，当节点 $x$ 下传标记到它的儿子 $ch$ 时，我们把儿子的标记更新为 $(add_{ch}+add_x,\min(v_{ch}+add_x,v_x))$即可。

- 换一种新的思路，我们发现这种方法的本质是把线段树上每个节点维护的元素分成了 **最大值** 和 **非最大值** 这两类，并对它们分别维护。区间最大值标记只会打在 $se<v<mx$ 的节点上，可以看成只针对最大值的加减操作；而区间加操作对于这两类值都生效。分别维护 **区间最大值的加减标记** 和 **非最大值的加减标记**，下传时判断当前节点是否为区间最大值即可。

其中后者看似麻烦一些，但思想很重要，可以扩展到更复杂的问题中（尤其是后面会提到的历史最值问题），因此最好也要理解。如果还不是很明白也没有关系，在下一道例题中会详细讲解。

之前的复杂度分析在这道题无法被沿用。论文中给出了一个基于对标记的分析的 $O(mlog^2n)$ 下界的证明，这个程序的实际运行效率是不错的。

### 同时支持区间最小值和最大值
[$BZOJ4695$. 最假女选手](https://darkbzoj.tk/problem/4695)


> 给出一个长度为 $n(n\leq 5\times 10^5)$ 的序列 $A$ 和 $m(m\leq 5\times 10^5)$ 次操作，每次操作为以下六种类型之一：
> 1. 给出 $l,r,k$，对于所有 $i\in[l,r]$，将 $A_i$ 加上 $k$
> 2. 给出 $l,r,k$，对于所有 $i\in[l,r]$，将 $A_i$ 变成 $\max(A_i,k)$
> 3. 给出 $l,r,k$，对于所有 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,k)$
> 4. 给出 $l,r$， 求 $\sum_{i=l}^{r}$
> 5. 给出 $l,r$，求序列 $A$ 区间 $[l,r]$ 的最大值
> 6. 给出 $l,r$，求序列 $A$ 区间 $[l,r]$ 的最小值

在这道题中，区间取 **最大值** 和 **最小值** 的操作同时出现了。虽然我们同样可以套用**第一道例题**的方法，维护区间加、区间取 $\max$，区间取 $\min$ 三个标记，但实现起来会很复杂（可以参考 [$OI-wiki$ 上的题解](https://oi-wiki.org/ds/seg-beats/#bzoj4695)）。这里我们可以仍考虑通过划分数域 **将区间最值操作转化为区间加减**。

应这道题的需要，我们将一个区间的元素划分为 **最大值**、**最小值**和 **其他值**三种。首先在每个节点上肯定要维护区间和 $sum$、区间最大值 $mx$ 和最小值 $mi$ 的信息，同时我们也要维护次大值 $semx$、次小值 $semi$ 和最大值最小值的个数 $cmx$,$cmi$。我们分别讨论题目中的三种修改操作。

- 对于加减操作，在线段树上定位区间后直接对三类值同时加上 $k$
- 对于取最小值操作，在线段树上暴力搜索找到 $semx<k<mx$ 的节点。这些节点对应的区间的最大值都应该改成 $k$，只对最大值加上 $k-mx$ 即可
- 取最大值操作同理

那么，我们需要分别维护这三个数域上的加减标记。但是有一些细节要注意：

- 以最大值上的加减标记为例。下传这个标记时要 **判断子区间内是否包含最大值**，如果 **不包含则应下传其他值的加减标记**
  
- 如果一个区间的值域很小（只有 $1$ 或 $2$ 个数），**可能会发生一个值既是最大值又是次小值这种情况**，也就是发生了数域的重叠。这种情况要特判，分辨到底该被哪个标记作用。

以上两点都会在下面的代码段中体现：
```cpp {.line-numbers}
// add1, add2, add3 分别表示最小值、最大值和其他值的加减标记。
// k1, k2, k3 也是按这个顺序。
void update(int o, int k1, int k2, int k3)
// 作用标记并合并标记，一定要注意顺序
{
    if (tr[o].mn1==tr[o].mx1)// 只有一种值时，最大值等于最小值
    {
        if (k1==k3) k1=k2; else k2=k1; // 不应被其他值的标记作用
        tr[o].sum+=1ll*k1*tr[o].cmn;
    }
    else tr[o].sum+=1ll*k1*tr[o].cmn+1ll*k2*tr[o].cmx
        +1ll*k3*(tr[o].r-tr[o].l+1-tr[o].cmn-tr[o].cmx);

    if (tr[o].mn2==tr[o].mx1) tr[o].mn2+=k2;
    // 次小值等于最大值，应该被最大值标记作用
    else if (tr[o].mn2!=INF) tr[o].mn2+=k3;
    // 否则应该被其他值标记作用

    if (tr[o].mx2==tr[o].mn1) tr[o].mx2+=k1;
    else if (tr[o].mx2!=-INF) tr[o].mx2+=k3;
    // 对次大值同理

    tr[o].mn1+=k1, tr[o].mx1+=k2;
    tr[o].add1+=k1, tr[o].add2+=k2, tr[o].add3+=k3;
}

void pushdown(int o) {// 下传标记
    int mn=min(tr[lc].mn1, tr[rc].mn1);
    int mx=max(tr[lc].mx1, tr[rc].mx1);
    // 找出最大值和最小值

    update(lc, tr[lc].mn1==mn?tr[o].add1:tr[o].add3,
           tr[lc].mx1==mx?tr[o].add2:tr[o].add3, tr[o].add3);
    // 下传标记到左子树，若左子树中有最大值则下传最大值加减标记，否则下传其他值加减标记。对最小值同理
    update(rc, tr[rc].mn1==mn?tr[o].add1:tr[o].add3,
           tr[rc].mx1==mx?tr[o].add2:tr[o].add3, tr[o].add3);
    // 右子树同理

    tr[o].add1=tr[o].add2=tr[o].add3=0;
}
```
https://www.luogu.com.cn/paste/092htzca

[P4198 楼房重建](https://www.luogu.com.cn/problem/P4198)
[UOJ#515. 【UR #19】前进四](https://uoj.ac/problem/515)
[BZOJ3064. Tyvj 1518 CPU监控](https://darkbzoj.tk/problem/3064)
[SP1557. GSS2 - Can you answer these queries II](https://www.spoj.com/problems/GSS2/)
[UOJ#164. 【清华集训2015】V](http://uoj.ac/problem/164)
[UOJ#169. 【UR #11】元旦老人与数列](http://uoj.ac/problem/169)
[P6242 【模板】线段树 3](https://www.luogu.com.cn/problem/P6242)