前言

线段树维护区间最值操作和区间历史最值。

魔改了论文中的证明,可能会有疏漏。

区间最值操作

区间取 min/max

(HDU 5306 Gorgeous Sequence)给定一个长度为 $n$ 的数组 $A$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets \min(A_i,x)$.
  • 给定 $l,r$,求 $\max_{i\in[l,r]} A_i$.
  • 给定 $l,r$,求 $\sum_{i\in[l,r]} A_i$.

$1\le n,m\le 10^6$.

对于线段树的一个区间 $[l,r]$,我们维护 $\operatorname{sum}(l,r)$,$\operatorname{fmax}(l,r)$,$\operatorname{smax}(l,r)$ 和 $\operatorname{cnt}(l,r)$ 分别表示这个区间的和、最大值,严格次大值(不存在则为 $-\infty$)和最大值的个数。

然后每次考虑把一个区间 $[l,r]$ 对 $x$ 取 $\min$ 会发生什么。

$\operatorname{GetMin}(l,r,x)$ 操作:

  • Case 1: $\operatorname{fmax}(l,r)\le x$,则该操作对此区间无影响。
  • Case 2: $\operatorname{smax}(l,r)<x<\operatorname{fmax}(l,r)$,则最大值改变,在此区间打上标记,然后令 $\operatorname{sum}(l,r)\gets \operatorname{sum}(l,r)+(x-\operatorname{fmax}(l,r))\operatorname{cnt}(l,r)$,$\operatorname{fmax}(l,r)\gets x$.
  • Case 3: $x\le \operatorname{smax}(l,r)$,直接递归左儿子右儿子进行修改,然后更新该区间的答案。

这样做的复杂度是多少呢?我们注意到显然由 Case 1 和 Case 2 结束的节点的个数和未结束节点的个数同阶(由于是二叉树,显然它们的个数只相差 $1$),所以只需要考虑需要处理 Case 3 的节点的情况。

可以发现,每次对一个区间进行 Case 3 中的处理时,必然导致该区间值域中的元素个数减少,于是我们考虑设势能函数 $\Phi(A)$ 表示 $A$ 建出的线段树每个区间值域中的元素个数之和。那么单次修改的时间复杂度为 $\mathcal O(-\Delta \Phi(A))$.

于是我们只需要考虑所有修改中 $\Phi (A)$ 的总增加量,我们注意到,在一次区间取 $\min$ 操作中,势能会增加(显然至多增加 $1$)的节点显然只可能是被我们执行了 $\operatorname{GetMin}$ 操作的区间的祖先,显然这样的节点数是 $\mathcal O(\log n)$ 个的。

刚开始的序列可以被视为给初始全为 $\infty$ 的 $A$ 进行了 $n$ 次修改,所以总的时间复杂度为 $\mathcal O((n+m)\log n)$.

区间取最值和区间最值操作

(Picks Loves Segment Tree)给定一个长度为 $n$ 的数组 $A$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets \min(A_i,x)$.
  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets A_i+x$($x$ 可能为负数).
  • 给定 $l,r$,求 $\sum_{i\in[l,r]} A_i$.

$1\le n,m\le 3\times 10^5$.

注意到,区间取 $\min$ 的标记(在上题 Case 2 中打上的标记)实际上是针对某个区间的最大值的加减标记,于是考虑把一个节点维护的元素分为两部分:最大值和非最大值,然后下传标记的时候直接传非最大值的加减标记,再判断子树中是否含有当前节点的最大值并下传最大值的加减标记即可。

然后区间加就很好做了:它是同时针对非最大值和最大值的加减标记。

接下来考虑复杂度,发现区间加最坏可能导致上述的势能函数增加 $\mathcal O(n)$,于是考虑换一种势能函数的定义。

考虑设 $\Phi(A)$ 表示 $A$ 建成的线段树中每个节点的势能之和,而定义一个代表区间 $[l,r]$ 节点的势能为满足以下条件中至少一个的权值 $x$ 的数量(${\rm mid}$ 表示区间终点):

  • 存在 $i\in[l,{\rm mid}],j\in({\rm mid}, r]$,$A_i=A_j=x$.
  • 存在 $i\notin [l,r]$,$A_i=x$.

将第 $i$ 次区间加 $x$ 视作区间加 $x + \varepsilon_i(\varepsilon_i\ll x,\varepsilon_i\ll \varepsilon_{i-1})$,其中 $\ll$ 表示远小于,显然并不影响每个位置的大小关系,并且每一次影响到某个节点的区间加操作必然不会使得其势能增加(未被修改和被修改了的节点一定不相等,而修改了的点的内部贡献不变)。

对于一次 $\operatorname{GetMin}(l,r,x)$ 操作。

考虑每个权值 $v$ 的贡献,我们实际上是先从代表 $[l,r]$ 的节点开始,走过一条长度为 $\mathcal O(\log n)$ 链(严格来说,应该是一个毛毛虫类似物,即一条链上挂了一些单点),到了某个节点 $u$,使得 $u$ 的左右子树中都包含 $v$。

此时,考虑 $v$ 的贡献,由于左右子树中都含 $v$,故 $u$ 的子树中权值 $v$ 对某个节点的势能产生贡献当且仅当其在该节点子树中出现。这个定义是与上题中定义等价的。

所以一次 $\operatorname{GetMin}(l,r,x)$ 的操作是 $\mathcal O(-\log n\Delta\Phi(A))$ 的。

于是可以分析得总的复杂度为 $\mathcal O(n\log n + m\log^2 n)$.

事实上,这个东西在实践中的表现是远低于上界的,也没人构造出能卡到严格 $\mathcal O(m\log^2n)$ 的数据。所以可以直接当一个 log 用。

区间历史最值

可以用懒标记处理的历史最值问题

给定一个长度为 $n$ 的数组 $A$ 和 $B$,且初始 $B_i=A_i$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets A_i+x$($x$ 可能为负数).
  • 给定 $l,r$,求 $\max_{i\in[l,r]} A_i$.
  • 给定 $l,r$,求 $\max_{i\in[l,r]} B_i$.

每次操作后令 $B_i\gets\max(B_i,A_i)$.

$1\le n,m\le 5\times 10^5$.

首先,我们对每个节点,要维护:$\operatorname{sum}(l,r)$,$\operatorname{max}(l,r)$ 和 $\operatorname{hmax}(l,r)$ 分别表示和,最大值以及历史最大值。

但是,假如我们仅仅维护 $\operatorname{tag}(l,r)$ 表示区间加标记的话,在传给孩子的时候并不知道如何更新孩子的历史最值。

于是,我们维护 $\operatorname{htag}(l,r)$ 表示 $\operatorname{tag}(l,r)$ 在上次下传前的历史最大值,这样在下传的时候,用 $\operatorname{sum}(v) + \operatorname{htag}(u)$ 去更新 $u$ 的孩子 $v$ 的历史最大值 $\operatorname{hmax}(v)$ 就好了。

显然,这样做的时间复杂度是 $\mathcal O((n+m)\log n)$.

(洛谷 P4314 CPU 监控)给定一个长度为 $n$ 的数组 $A$ 和 $B$,且初始 $B_i=A_i$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets x$.
  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets A_i + x$.
  • 给定 $l,r$,求 $\max_{i\in[l,r]} A_i$.
  • 给定 $l,r$,求 $\max_{i\in[l,r]} B_i$.

每次操作后令 $B_i\gets\max(B_i,A_i)$.

$1\le n,m\le 10^5$.

在区间加减标记 $\operatorname{add}$ 和区间最大加减标记 $\operatorname{hadd}$ 的基础上,维护区间赋值标记 $\operatorname{asign}$ 和区间历史最大赋值标记 $\operatorname{hasign}$。然后令赋值标记的优先级在加减标记上。

推标记的时候:

  • 先推 $\operatorname{add}$。若推到了有 $\operatorname{asign}$ 标记的节点,则直接加在 $\operatorname{asign}$ 标记上;若推到了没有 $\operatorname{asign}$ 标记的节点,则加在 $\operatorname{add}$ 标记上。
  • 再推 $\operatorname{asign}$。若推到了存在 $\operatorname{add}$ 标记的节点,则清空该标记。但注意保留 $\operatorname{hadd}$ 标记不变。

没有提到的历史版本的标记也是类似的,这里不再展开说明。

时间复杂度 $\mathcal O((n+m)\log n)$.

(洛谷 P6242 线段树 3)给定一个长度为 $n$ 的数组 $A$ 和 $B$,且初始 $B_i=A_i$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets A_i+x$.
  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets \min(A_i,x)$.
  • 给定 $l,r$,求 $\sum_{i\in[l,r]} A_i$.
  • 给定 $l,r$,求 $\max_{i\in[l,r]} A_i$.
  • 给定 $l,r$,求 $\max_{i\in[l,r]} B_i$.

每次操作后令 $B_i\gets\max(B_i,A_i)$.

$1\le n,m\le 5\times 10^5$.

在先前的过程中,我们已经得到了一个使用一个 $\log$ 的代价,将区间最值操作问题转化为对每个节点最大值的操作问题的方法。

于是直接套用这个方法,维护每个节点最大值、非最大值的加减标记、历史最大加减标记。

然后我们就做到了 $\mathcal O(n\log n + m\log^2n)$ 的时间复杂度。

代码:

#define cnt(o) T[o].cnt
#define sum(o) T[o].sum
#define fmax(o) T[o].fmax
#define nmax(o) T[o].nmax
#define h_max(o) T[o].h_max
#define tag_fmax(o) T[o].tag_fmax
#define tag_nmax(o) T[o].tag_nmax
#define htag_fmax(o) T[o].htag_fmax
#define htag_nmax(o) T[o].htag_nmax
typedef long long ll;
typedef double ff;
typedef std::pair <int, int> pii;
const int N = 5e5 + 5, Inf = 0x3f3f3f3f;

struct Node {
    ll sum;
    int cnt, fmax, nmax, tag_fmax, tag_nmax,
        h_max, htag_fmax, htag_nmax;
    Node() { fmax = nmax = h_max = -Inf; }
} T[N << 3];
void Update(int o) {
    cnt(o) = 0; sum(o) = sum(o << 1) + sum(o << 1 | 1);
    fmax(o) = std::max(fmax(o << 1), fmax(o << 1 | 1));
    nmax(o) = std::max(nmax(o << 1), nmax(o << 1 | 1));
    if(fmax(o << 1) == fmax(o)) cnt(o) += cnt(o << 1);
    else nmax(o) = std::max(nmax(o), fmax(o << 1));
    if(fmax(o << 1 | 1) == fmax(o)) cnt(o) += cnt(o << 1 | 1);
    else nmax(o) = std::max(nmax(o), fmax(o << 1 | 1));
    h_max(o) = std::max(h_max(o << 1), h_max(o << 1 | 1));
}
void Build(int o, int l, int r, int A[]) {
    if(l < r) {
        int mid = (l + r) >> 1;
        Build(o << 1, l, mid, A);
        Build(o << 1 | 1, mid + 1, r, A);
        Update(o);
    } else {
        sum(o) = fmax(o) = h_max(o) = A[l];
        nmax(o) = -Inf; cnt(o) = 1;
    }
}
void ApplyTag(int o, int l, int r, int add_fmax, int add_nmax, int hadd_fmax, int hadd_nmax) {
    sum(o) += 1LL * cnt(o) * add_fmax + 1LL * (r - l + 1 - cnt(o)) * add_nmax;
    htag_fmax(o) = std::max(htag_fmax(o), tag_fmax(o) + hadd_fmax);
    htag_nmax(o) = std::max(htag_nmax(o), tag_nmax(o) + hadd_nmax);
    h_max(o) = std::max(h_max(o), fmax(o) + hadd_fmax);
    tag_fmax(o) += add_fmax; tag_nmax(o) += add_nmax;
    fmax(o) += add_fmax; if(nmax(o) > -Inf) nmax(o) += add_nmax;
}
void PushTag(int o, int l, int r) {
    int mid = (l + r) >> 1, t_max = std::max(fmax(o << 1), fmax(o << 1 | 1));
    if(fmax(o << 1) == t_max)
        ApplyTag(o << 1, l, mid, tag_fmax(o), tag_nmax(o), htag_fmax(o), htag_nmax(o));
    else ApplyTag(o << 1, l, mid, tag_nmax(o), tag_nmax(o), htag_nmax(o), htag_nmax(o));
    if(fmax(o << 1 | 1) == t_max)
        ApplyTag(o << 1 | 1, mid + 1, r, tag_fmax(o), tag_nmax(o), htag_fmax(o), htag_nmax(o));
    else ApplyTag(o << 1 | 1, mid + 1, r, tag_nmax(o), tag_nmax(o), htag_nmax(o), htag_nmax(o));
    tag_fmax(o) = tag_nmax(o) = htag_fmax(o) = htag_nmax(o) = 0;
}
void GetMin(int o, int l, int r, int v) {
    PushTag(o, l, r);
    if(v >= fmax(o)) return;
    if(v > nmax(o)) {
        ApplyTag(o, l, r, v - fmax(o), 0, v - fmax(o), 0);
        return;
    }
    int mid = (l + r) >> 1;
    GetMin(o << 1, l, mid, v);
    GetMin(o << 1 | 1, mid + 1, r, v);
    Update(o);
}
void Modify(int o, int l, int r, int ql, int qr, int v, int typ) {
    if(ql <= l && r <= qr) {
        if(typ == 1) ApplyTag(o, l, r, v, v, v, v);
        else if(typ == 2) GetMin(o, l, r, v);
    } else {
        int mid = (l + r) >> 1;
        PushTag(o, l, r);
        if(ql <= mid) Modify(o << 1, l, mid, ql, qr, v, typ);
        if(qr > mid) Modify(o << 1 | 1, mid + 1, r, ql, qr, v, typ);
        Update(o);
    }
}
int QueryMax(int o, int l, int r, int ql, int qr, int typ) {
    if(ql <= l && r <= qr) {
        if(typ == 4) return fmax(o);
        else if(typ == 5) return h_max(o);
        else return -Inf;
    } else {
        int mid = (l + r) >> 1, ret = -Inf;
        PushTag(o, l, r);
        if(ql <= mid) ret = std::max(ret, QueryMax(o << 1, l, mid, ql, qr, typ));
        if(qr > mid) ret = std::max(ret, QueryMax(o << 1 | 1, mid + 1, r, ql, qr, typ));
        return ret;
    }
}
ll QuerySum(int o, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return sum(o);
    else {
        int mid = (l + r) >> 1; ll ret = 0;
        PushTag(o, l, r);
        if(ql <= mid) ret += QuerySum(o << 1, l, mid, ql, qr);
        if(qr > mid) ret += QuerySum(o << 1 | 1, mid + 1, r, ql, qr);
        return ret;
    }
}

int A[N];
int main() {
    int n, q;
    rd(n, q);
    for(int i = 1; i <= n; ++i) rd(A[i]);
    Build(1, 1, n, A);
    while(q--) {
        int typ, l, r, v;
        rd(typ);
        if(typ == 1 || typ == 2) {
            rd(l, r, v);
            Modify(1, 1, n, l, r, v, typ);
        } else if(typ == 3) {
            rd(l, r);
            printf("%lld\n", QuerySum(1, 1, n, l, r));
        } else if(typ == 4 || typ == 5) {
            rd(l, r);
            printf("%d\n", QueryMax(1, 1, n, l, r, typ));
        }
    }
    return 0;
}

历史最值的区间问题

给定一个长度为 $n$ 的数组 $A$ 和 $B$,且初始 $B_i=A_i$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets A_i+x$.
  • 给定 $l,r$,求 $\sum_{i\in[l,r]} B_i$.

每次操作后令 $B_i\gets\max(B_i,A_i)$.

$1\le n,m\le 5\times 10^5$.

我们设一个辅助数组 $C$,每次令 $C_i\gets A_i-B_i$,则区间加相当于区间最值操作:$C_i\gets \min(C_i+x,0)$。查询时的答案即为 $A$ 的区间和加上 $B$ 的区间和,可以用先前的方法维护。

时间复杂度 $\mathcal O(n\log n + m\log^2n)$.

给定一个长度为 $n$ 的数组 $A$ 和 $B$,且初始 $B_i=A_i$,支持以下操作共 $m$ 个:

  • 给定 $l,r,x$,对 $i\in[l,r]$,令 $A_i\gets A_i+x$.
  • 给定 $l,r$,求 $\sum_{i\in[l,r]} B_i$.

每次操作后令 $B_i\gets B_i+A_i$.

$1\le n,m\le 5\times 10^5$.

我们定义辅助数组 $C$,满足 $C_i\gets B_i-tA_i$,其中 $t$ 为当前的操作数。

那么一次区间修改相当于对 $C$ 区间加减 $tx$,可以简单地用线段树维护。

参考资料

最后修改:2021 年 03 月 22 日 09 : 00 AM