区间最值操作 & 区间历史最值

本文讲解了吉老师在 2016 年集训队论文（见参考资料）中提到的使用线段树维护区间最值操作和区间历史最值的方法。

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

区间最值操作

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

HDU5306. Gorgeous Sequence

给出一个长度为 n(n\leq 10^6) 的序列 A 和 m(m\leq 10^6) 次操作，每次操作为以下三种类型之一：

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 \min(A_i,k)；

给出 l,r，求序列 A 区间 [l,r] 的最大值；

给出 l,r，求 \sum_{i=l}^{r}A_i。

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

考虑到区间取 \min 的操作只会对最大值不超过 k 的节点产生影响，我们可以在这方面产生思路。为了使复杂度变对，线段树的一个节点要维护三个信息：区间最大值 mx，区间严格次大值 se 和最大值的个数 cnt。那么，一次区间最值操作作用在这个节点上时，可以被分为以下三种情况：

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

举个例子，现在要以 k=2 对下面这棵线段树维护的区间取 \min。每个节点左侧表示区间最大值，右侧表示严格次大值。（很抱歉用了吉老师论文里的例子，因为我实在找不出比它更适合做例子的例子了）

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

这样做的复杂度可以证明是 O(m\log n) 的。原论文的证明使用了势能分析，这里给出一种更好懂的 O((n+m)\log n) 下界的证明：

显然只有暴力 DFS 的过程会影响复杂度，我们考虑一次区间最值操作中哪些节点会被搜索到。发现到达的节点区间中不同的数的个数（下称“值域”）一定会减少（因为至少将最大值与次大值合并了）。线段树每层节点表示的区间的值域一共是 O(n) 的，一共 \log 层加起来就是 O(n\log n)。再加上每次操作的复杂度，可以得到复杂度的一个下界为 O((n+m)\log n)。

为了方便理解，下面给出这道题区间修改打标记的代码：

void update(int o, int k) // 只打标记不下传
{
    if (k<tr[o].mx)
    // 这里需要判一下当前节点是否为最大值
    {
        tr[o].sum+=(1ll*k-tr[o].mx)*tr[o].cnt;
        tr[o].mx=tr[o].tag=k;
    }
}

void pushdown(int o) // 下传标记到左右子树
{
    if (~tr[o].tag)
    {
        update(lc, tr[o].tag);
        update(rc, tr[o].tag);
        tr[o].tag=-1; // 这个题里没有负数，把标记清为 -1 即可
    }
}

void modify(int o, int l, int r, int k)
{
    if (tr[o].l>r||tr[o].r<l||k>=tr[o].mx) return; // 情况 1
    if (l<=tr[o].l&&tr[o].r<=r&&k>tr[o].se)
    { update(o, k); return; } // 情况 2
    pushdown(o);
    modify(lc, l, r, k), modify(rc, l, r, k); // 继续在子树内搜索
    pushup(o);
}

支持区间加减

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

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

套用上一题的做法，我们只需把标记换成二元组 (add, v)，表示将当前节点维护的区间先加上 add 再与 v 取最小值。合并标记时，先考虑给当前节点加上一个标记，我们除了更新当前节点的区间加标记 add，还需要把它加到 v 上；而给当前节点取最小值可以直接将标记对它取 \min。形式地说，当节点 x 下传标记到它的儿子 ch 时，我们把儿子的标记更新为 (add_{ch}+add_x,\min(v_{ch}+add_x,v_x)) 即可。
换一种新的思路，我们发现这种方法的本质是把线段树上每个节点维护的元素分成了最大值和非最大值这两类，并对它们分别维护。区间最大值标记只会打在 se<v<mx 的节点上，可以看成只针对最大值的加减操作；而区间加操作对于这两类值都生效。分别维护区间最大值的加减标记和非最大值的加减标记，下传时判断当前节点是否为区间最大值即可。

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

由于区间加减操作，某些节点的值域会增大。一次操作区间加减最多会影响 O(\log^2n) 个节点的值域（比如对区间 [2,n-1] 操作），所以用之前的证明方法可证复杂度的一个上界为 O(n\log n+m\log^2n)（论文里给的是 O(m\log^2n)）。而实际实现时会发现这个上界其实往往是跑不满的。

同时支持区间最小值和最大值

BZOJ4695. 最假女选手

给出一个长度为 n(n\leq 5\times 10^5) 的序列 A 和 m(m\leq 5\times 10^5) 次操作，每次操作为以下六种类型之一：

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 加上 k；

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 \max(A_i,k)；

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 \min(A_i,k)；

给出 l,r，求 \sum_{i=l}^{r}A_i；

给出 l,r，求序列 A 区间 [l,r] 的最大值；

给出 l,r，求序列 A 区间 [l,r] 的最小值。

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

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

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

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

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

以上两点都会在下面的代码段中体现：

// 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;
}

小结

这里再次强调，上面的这种处理区间最值的方法的核心是数域的划分。也就是说，我们以一个 \log 的代价，将区间最值操作转化成了最值数域上的区间加减操作。本文的后半部分将会继续应用这种思想。

区间历史最值

对于序列 A 的某个位置 i，它的历史最值是指 A_i 从初始化到当前达到的最大值 / 最小值，或者每一次修改操作后的值之和。我们把这三种分别称作历史最大值、历史最小值和历史版本和。

而区间历史最值则是指求序列 A 的历史最值的最大值 / 最小值或者代数和等的区间问题。其中最大值和最小值的维护方式与单点问题相同，比较容易处理；而求和则需要一步转化，本文暂时不提，以后可能会补充。

沿用懒标记

对于一些修改操作不复杂的问题（区间加，区间覆盖等），我们可以沿用懒标记的做法。这是最基本也是最重要的一种做法。

BZOJ3064. Tyvj 1518 CPU监控

给出一个长度为 n(n\leq 10^5) 的序列 A，定义辅助数组 B，初始时与 A 完全相同。给出 m(m\leq 10^5) 次操作，每次操作为以下四种类型之一：

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 加上 k；

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 k；

给出 l,r，求序列 A 区间 [l,r] 的最大值；

给出 l,r，求序列 B 区间 [l,r] 的最大值。

每次操作后，对于所有 i，将 B_i 变成 \max(B_i,A_i)。

发现序列 B 就是序列 A 的历史最大值，那么第四种操作询问的就是 [l,r] 中历史最大值的最大值。

先考虑区间加操作，我们在线段树的每个节点上维护两个值：区间当前最大值 mx 和历史最大值 mx'，以及两个标记：区间加标记 add 和历史最大加减标记 add'。这里唯一不容易理解的就是“历史最大加减标记”，它表示的是从上一次下传 add 到现在，区间加标记达到的最大值。

考虑历史最值标记的合并。当节点 x 下传标记到它的儿子 ch 时，儿子历史最大值应与当前值取 \max，写成公式就是下面的样子：

\begin{array}{} add'_{ch}\gets\max(add'_{ch},add_{ch}+add'_x)\\ mx'_{ch}\gets \max(mx'_{ch},mx_{ch}+add'_x) \end{array}

现在加入区间覆盖操作，我们把标记换成二元组 (add,cov)，表示将当前区间先加上 add 再全部变成 cov。这个标记是可以合并的：如果一个区间已经被覆盖成了一个值，那么区间加操作可以转化为区间覆盖操作，直接把它加到 cov 上即可。同理，我们还需要维护 (add',cov')，表示上一次下传这个节点的标记到现在，第一阶段区间加的最大值为 add'，第二阶段区间覆盖的最大值为 cov'。

这里给出打标记和下传标记部分的代码：

// 以下代码段中，所有带下划线的变量都是历史最值
void plus(int o, int k, int k_) // 区间加标记
{
    tr[o].mx_=max(tr[o].mx_, tr[o].mx+k_), tr[o].mx+=k;
    // 更新历史最大值和当前最大值，这里要注意顺序
    if (!tr[o].tag)
        tr[o].add_=max(tr[o].add_, tr[o].add+k_), tr[o].add+=k;
    // 如果没有区间覆盖标记，正常更新 add 标记
    else tr[o].cov_=max(tr[o].cov_, tr[o].cov+k_), tr[o].cov+=k;
    // 否则直接加到 cov 上
}

void cover(int o, int k, int k_) // 区间覆盖标记
{
    tr[o].mx_=max(tr[o].mx_, k_), tr[o].mx=k;
    tr[o].cov_=max(tr[o].cov_, k_), tr[o].cov=k, tr[o].tag=1;
}

void pushdown(int o) // 下传标记
{
    if (tr[o].add)
    {
        plus(lc, tr[o].add, tr[o].add_);
        plus(rc, tr[o].add, tr[o].add_);
        tr[o].add=tr[o].add_=0;
    }
    if (tr[o].tag) // 这里的 tag 表示当前节点有没有区间覆盖标记
    {
        cover(lc, tr[o].cov, tr[o].cov_);
        cover(rc, tr[o].cov, tr[o].cov_);
        tr[o].tag=0, tr[o].cov_=INT_MIN;
    }
}

所有操作的复杂度都和普通线段树一致，总共是 O(m\log n) 的。

此外，有些数据结构问题可以离线后转化为这种历史最值问题，下面是一道例题。

SP1557. GSS2 - Can you answer these queries II

给出长度为 n(n\leq 10^5) 的序列 A 和 q(q\leq 10^5) 次询问，每次询问给出 [l,r]，求区间 [l,r] 相同数只算一次 的最大子段和。序列 A 的值域为 [-10^5,10^5]。

这道题用常规方法不好快速解决，我们考虑离线。

将询问按 r 从小到大排序。对于普通的最大子段和问题，我们可以逐个加入下标不大于 r 的元素，对于每个位置 i 维护以 i 为左端点的区间元素和的最大值。观察加数的过程，可以看出这个值就是区间 [i,n] 的元素和的历史最大值。用线段树维护，发现加入下标为 k 的元素就相当于把区间 [1,k] 加上 A_i，那么问题就转化为区间加、区间求历史最大值的最大值。而有了相同数只算一次的限制，我们不妨只考虑某个数在 [i,n] 中第一次出现的位置，那么加入第 k 个数就只需要将区间 [pre_{A_i}+1,k] 加上 A_i 就可以了，其中 pre_{A_i} 表示 A_i 上一次出现的位置。同样处理即可，复杂度 O(m\log n)。

与区间最值操作结合

在有些题目中，区间历史最值的询问会与本文第一部分讲解的区间最值操作同时出现。我们考虑这种问题的解决方法，通常可以分为下面的两类。

区间最值操作与历史最值询问同向

UOJ#164. 【清华集训2015】V

给出一个长度为 n(n\leq 5\times 10^5) 的序列 A，定义辅助数组 B，初始时与 A 完全相同。给出 m(m\leq 5\times 10^5) 次操作，每次操作为以下五种类型之一：

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 加上 k；

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 \max(A_i-k,0)；

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 k；

给出 p，询问 A_p；

给出 p，询问 B_p。

每次操作后，对于所有 i，将 B_i 变成 \max(B_i,A_i)。

定义标记 (add,v) 表示将一个区间先加上 add 再与 v 取最大值，我们发现题目中的三种修改都可以用这种标记表示，分别是 (k,0),(-k,0),(-\infty,k)。此时我们说区间最值操作与历史最值询问同向，因为一个是取最大值，另一个是求历史最大值。这种标记的合并方式在前文已经提到过了，在此不再赘述。而维护历史最大值时，可以把标记看成自变量是当前值的分段函数，它的前半是水平的直线，后半段是斜率为 1 的直线。更新历史最大标记时就要对这两个函数取 \max，如下图：

其中红色段表示两个函数的最大值。容易发现这个最大值也是一个类似的两段函数，我们直接把 add 和 v 分别取 \max 就可以更新历史标记了。复杂度仍是和普通线段树一样的 O(m\log n)。

区间最值操作与历史最值询问反向

UOJ#169. 【UR #11】元旦老人与数列

给出一个长度为 n(n\leq 5\times 10^5) 的序列 A，定义辅助数组 B，初始时与 A 完全相同。给出 m(m\leq 5\times 10^5) 次操作，每次操作为以下四种类型之一：

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 加上 k；

给出 l,r,k，对于所有 i\in[l,r]，将 A_i 变成 \max(A_i,k)；

给出 l,r，求序列 A 区间 [l,r] 的最小值；

给出 l,r，求序列 B 区间 [l,r] 的最小值。

每次操作后，对于所有 i，将 B_i 变成 \max(B_i,A_i)。

这道题与上一道例题的最大区别在于区间最值操作与历史最值询问是反向的，因为一个是取最大值，而另一个是求历史最小值。如果用上一题的方法维护历史标记的话，两个函数取最小值就会出现下图的情况：

其中紫色段表示两个函数的最小值。可以看出这样合并会导致函数段数无限增长，就不好维护了。我们需要其他的方法。

本文上一部分提到了一种通过划分数域把区间最值操作转化为区间加减的方法。在这里我们需要把一个区间的元素划分成最小值和非最小值两部分。那么区间最值操作可以转化为对最小值的加减操作，而题目中的区间加减则同时作用于这两类值。于是我们以一个 \log 的代价把问题就变成了两个数域上的区间加减操作和历史最值询问，也就是 CPU 监控 那道题了。具体地说，我们需要维护四种标记：

最小值加减标记
最小值历史最小的加减标记
非最小值加减标记
非最小值历史最小的加减标记

前两个标记是只修改最小值的，所以下传时要判断当前节点是否包含区间最小值，这也在前文例题中提到了。复杂度为 O(m\log^2 n)，需要注意一下常数。

本文内容到此就结束了。所有有名字的例题的笔者的完整 AC 代码可以在这里看到。

参考资料

2016 年 IOI 国家集训队论文——吉如一《区间最值操作与历史最值问题》
OI-wiki 中”区间最值操作 & 区间历史最值“页面

冷滟泽的个人博客

区间最值操作 & 区间历史最值学习笔记

区间最值操作 & 区间历史最值