GLFLS课程：线段树进阶

线段树合并与分裂

线段树合并

两个权值线段树 \(T_1\) 和 \(T_2\) 的合并是一个递归的过程。我们不妨设要合并的子树为 \(x\) 和 \(y\)，其对应区间均为 \([l,\ r]\) 那么分类讨论如下：

  \((1)\) 首先若 \(x = 0\) 或 \(y = 0\)，则 \(x\)， \(y\) 中有空节点，直接返回 \(x + y\) 即可。

  \((2)\) 再将 \(x,\ y\) 的左和右儿子分别合并，令合并后的节点编号分别为 \(p,\ q\)。

  \((3)\) 将 \(y\) 的左儿子设为 \(p\)，右儿子设为 \(q\)，完成合并。返回 \(y\)。

特别的，当 \(x\) 或 \(y\) 为叶子时，直接合并信息。在合并过程中，需要实时 pushdown/spread 与 pushup。

线段树合并的时间复杂度与删去的节点数同级。

\(Code:\)

int merge(int x, int y, int pl, int pr){
    if(!x || !y) return x | y; // or x + y
    if(pl == pr){
        tree[y].sum += tree[x].sum;
        return y;
    }
    int mid = (pl + pr) / 2;
    tree[y].ls = merge(tree[x].ls, tree[y].ls, pl, mid), tree[y].rs = merge(tree[x].rs, tree[y].rs, mid + 1, pr);
    pushup(y);
    return y;
    // Due to single update, pushdown isn't required.
    // If your func isn't a single update one, DO remember to pushdown!
}

\(Template: P4556.\)

线段树维护区间最值和历史最大值

经典例题：Gorgeous Sequence (hdu 5306)

一个长度为 \(n\) 的序列 \(a\)， 做 \(m\) 次操作，操作有以下 3 种：
$0\ L\ R\ x $ 即对于 \([L,\ R]\) 区间内的每个 \(a_i\)， 用 \(min(a_i,\ x)\) 替换；
\(1\ L\ R\) 即输出 \([L,\ R]\) 区间内的最大值 \(a_i\)；
\(2\ L\ R\) 即输出 \([L,\ R]\) 区间内所有 \(a_i\) 的和。

对于线段树的每一个节点，我们需要定义标记：区间和 sum， 区间最大值 maxn， 最大值个数 num， 严格次大值 submaxn。

做区间最值的第 0 种修改操作， 用 min(a[i], x) 替换区间 \([L,\ R]\) 中的每一个 \(a_i\)。

我们对区间的每一个节点进行剪枝搜索，对于某个节点，我们分以下3类进行讨论：

  \((1)\) 当 $maxn \le x $ 时，这次不产生修改，退出。

  \((2)\) 当 \(submaxn < x < maxn\) 时，这次修改会影响最大值，更新 sum = sum - t(maxn - x)，maxn = x，打上 lazy_tag 后退出。

  \((3)\) 当 \(submaxn \ge x\) 时，无法直接更新，只能递归其左右儿子。

01:48:57