从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法

· · 个人记录

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html。

首先需要申明的是，真的是浅谈，因为我对这个算法的认识还是非常低的。

既然是从《楼房重建》出发，那么当然是先看看这道题：

[清华集训2013]楼房重建

bzoj 链接

题意简述：

有 n 栋楼，第 i 栋的高度为 H_i，也就是说第 i 栋楼可以抽象成一条两端点为 (i, 0) 和 (i, H_i) 的线段。

初始时 H_i 均为 0，要支持动态修改单点的 H_i。

每次询问从 O(0, 0) 点可以看到多少栋楼房。

能看到一栋楼 i 当且仅当 H_i > 0 且 (0, 0) 与 (i, H_i) 的连线上不经过其它楼房。

题解：

令 s_i = H_i / i，即 (0, 0) 到 (i, H_i) 的斜率，再定义 s_0 = 0。

则一栋楼房 i 能被看见，当且仅当 \displaystyle \max_{j = 0}^{i - 1} \{ s_j \} < s_i，也就是说它是 s_i 的前缀严格最大值。

直接进入正题，我们使用线段树维护这个东西。

考虑线段树上的某一个节点表示的区间 [l, r]，则保存的信息有：

  1. 这个区间中的 s_i 的最大值。
  2. 仅考虑这个区间时的上述答案，也就是不考虑 [1, l - 1] 对本区间的影响，而是看作整体的前缀最大值个数。

可以发现只有单点修改，那么我们只需考虑递归到底层节点后，一层层往上维护信息即可。

当前考虑一个节点 i，假设 i 的子树内的所有节点（除了 i 本身）的信息都维护好了，需要维护节点 i 的信息。

信息 1 是容易维护的，只要两个子树取 \max 即可。

但是信息 2 如果直接用两个子树信息相加，是错误的，因为没有考虑左子树向右子树的贡献。

进一步分析：可以发现直接继承左子树的信息是没问题的，但是右子树信息不能直接继承。

考虑引入一个新函数：\mathrm{calc}(i, pre)，它的作用是返回 i 子树内，考虑了前缀最大值 pre 的影响后的答案。

为了方便表述，把信息 1 记做 \boldsymbol{\max[i]}，把信息 2 记做 \boldsymbol{\mathrm{cnt}[i]}，则它的伪代码如下：

\displaystyle \begin{array}{l} \textbf{def: } \mathrm{calc}(i, pre) \\ \qquad \textbf{if } (i \text{ is a leaf node}) \\ \qquad \qquad \textbf{return } {\color{green}{[\max[i] > pre]}} \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if } (\max[\mathrm{leftchild}[i]] > pre) \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{\mathrm{calc}(\mathrm{leftchild}[i], pre)}} + {\color{red}{(\mathrm{cnt}[i] - \mathrm{cnt}[\mathrm{leftchild}[i]])}} \\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{0}} + {\color{red}{\mathrm{calc}(\mathrm{rightchild}[i], pre)}} \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array}

其中蓝色的是左子树贡献，红色的是右子树贡献。

当当前节点 i 是叶节点的时候，贡献很容易计算。
否则考虑左右子树的贡献分别计算，分成两种情况考虑：

  1. 此时对右子树来说，$pre$ 是无意义的，所以递归进左子树，右子树的贡献直接用“全部”减“左子树”计算即可。
  2. 此时对左子树来说，就不可能贡献任何前缀最大值了，所以贡献为 $0$，然后递归进右子树即可。

可以看出，调用一次 \mathrm{calc} 函数递归的时间复杂度为 \mathcal O (\log n)，因为每次只递归进一个孩子。

每次维护当前节点的答案时，只要令 \mathrm{cnt}[i] = \mathrm{cnt}[\mathrm{leftchild}[i]] + \mathrm{calc}(\mathrm{rightchild}[i], \max[\mathrm{leftchild}[i]]) 即可。

可以发现有 \mathcal O (\log n) 个节点要调用 \mathrm{calc} 函数，所以一次单点修改的时间复杂度为 \mathcal O (\log^2 n)。

至此可以写出本题的代码：

#include <cstdio>

typedef long long LL;
const int MN = 100005, MS = 1 << 18 | 7;

int N, Q, H[MN];

inline bool gt(int p1, int p2) { // s[p1] is greater than s[p2]
    if (!p2) return H[p1];
    return (LL)H[p1] * p2 > (LL)H[p2] * p1;
}
#define li (i << 1)
#define ri (li | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
int id[MS], cnt[MS];
void Build(int i, int l, int r) {
    id[i] = l, cnt[i] = 1;
    if (l == r) return ;
    Build(ls), Build(rs);
}
int Calc(int i, int l, int r, int p) {
    if (l == r) return gt(l, p);
    if (gt(id[li], p)) return Calc(ls, p) + (cnt[i] - cnt[li]);
    else return 0 + Calc(rs, p);
}
void Mdf(int i, int l, int r, int p) {
    if (l == r) return ;
    if (p <= mid) Mdf(ls, p);
    else Mdf(rs, p);
    id[i] = gt(id[ri], id[li]) ? id[ri] : id[li];
    cnt[i] = cnt[li] + Calc(rs, id[li]);
}

int main() {
    scanf("%d%d", &N, &Q);
    Build(1, 1, N);
    while (Q--) {
        int p, x;
        scanf("%d%d", &p, &x);
        H[p] = x, Mdf(1, 1, N, p);
        printf("%d\n", Calc(1, 1, N, 0));
    }
    return 0;
}

但是，我们注意到一个很关键的性质：

当 pre 小于左子树的最大值时，右子树对当前节点的贡献，是通过减法计算的。

也就是说这个信息要满足一定程度上的可减性。

但是有很多信息是不满足可减性的，比如 \max, \min、按位与、按位或等。

为了能让这种线段树适应更一般的情况，我们修改维护的信息的意义：

  1. 仍然维护这个区间中的 s_i 的最大值。
  2. 此时并不是维护区间的答案，而是仅考虑该区间的影响后，却又只统计右子树的答案。
    也就是说令当前节点对应的区间为 [l, r]，区间中点为 mid，则：
    维护的答案是，只考虑 g_l \sim g_r 时，在区间 [mid + 1, r] 中的答案。

仍然把信息 1 记做 \max[i]，把信息 2 记做 \mathrm{cnt}[i]。

对于叶节点，信息 2 则看作是未定义的。

然后考虑维护当前节点的信息（也就是 Pushup），仍然引入一个 \mathrm{calc}(i, pre) 函数。

此时它的作用仍然是计算在 pre 的影响下的整个区间内的答案（而不是右子树），也就是说它的意义没有改变。

它的伪代码如下：

\displaystyle \begin{array}{l} \textbf{def: } \mathrm{calc}(i, pre) \\ \qquad \textbf{if } (i \text{ is a leaf node}) \\ \qquad \qquad \textbf{return } {\color{green}{[\max[i] > pre]}} \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if } (\max[\mathrm{leftchild}[i]] > pre) \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{\mathrm{calc}(\mathrm{leftchild}[i], pre)}} + {\color{red}{\mathrm{cnt}[i]}} \\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } {\color{blue}{0}} + {\color{red}{\mathrm{calc}(\mathrm{rightchild}[i], pre)}} \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array}

其实变化并不大，因为此时 \mathrm{cnt}[i] 记录的直接就是右子树信息，所以不需要做减法。

每次维护当前节点的答案时，只要令 \mathrm{cnt}[i] = \mathrm{calc}(\mathrm{rightchild}[i], \max[\mathrm{leftchild}[i]]) 即可。

其实更好写了，代码如下：

#include <cstdio>

typedef long long LL;
const int MN = 100005, MS = 1 << 18 | 7;

int N, Q, H[MN];

inline bool gt(int p1, int p2) { // s[p1] is greater than s[p2]
    if (!p2) return H[p1];
    return (LL)H[p1] * p2 > (LL)H[p2] * p1;
}
#define li (i << 1)
#define ri (li | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
int id[MS], cnt[MS];
void Build(int i, int l, int r) {
    id[i] = l, cnt[i] = 1;
    // if i is a leaf node, then cnt[i] can be any value.
    // but here, for convenience, we just let it be 1.
    if (l == r) return ;
    Build(ls), Build(rs);
}
int Calc(int i, int l, int r, int p) {
    if (l == r) return gt(l, p);
    if (gt(id[li], p)) return Calc(ls, p) + cnt[i];
    else return 0 + Calc(rs, p);
}
void Mdf(int i, int l, int r, int p) {
    if (l == r) return ;
    if (p <= mid) Mdf(ls, p);
    else Mdf(rs, p);
    id[i] = gt(id[ri], id[li]) ? id[ri] : id[li];
    cnt[i] = Calc(rs, id[li]);
}

int main() {
    scanf("%d%d", &N, &Q);
    Build(1, 1, N);
    while (Q--) {
        int p, x;
        scanf("%d%d", &p, &x);
        H[p] = x, Mdf(1, 1, N, p);
        printf("%d\n", Calc(1, 1, N, 0));
    }
    return 0;
}

[CodeForces 671E]Organizing a Race

CF 链接

题意简述：

题意的抽象过程太复杂了，这里仅考虑抽象后的模型：

给出两个长度为 n 的整数序列 a_i, b_i，令 \displaystyle c_i = a_i + \max_{j = 1}^{i} \{ b_j \}。

你需要动态维护整个数组中满足 \boldsymbol{c_i \le k} 的最大下标 \boldsymbol{i}，需要支持 b_i 的区间加减的修改操作。

而 a_i 是不会变的（不过，如果加一个 a_i 的区间加减操作，也可以做）。

题解：

可以发现，因为这里要维护的东西变成 c_i 的区间 \min 了，没有可减性，所以不能用第一种方法。

考虑在线段树的每个节点维护三个信息：

  1. 这个区间中 a_i 的最小值，记做 {a\mathrm{min}}。
  2. 这个区间中 b_i 的最大值，记做 {b\mathrm{max}}。
  3. 仅考虑该区间时，在右子树内的答案，记做 \mathrm{ans}。

因为是区间修改 b_i，所以这里需要用到线段树懒标记的方法，具体不展开讲。

此时需要面对两个问题，下传标记（Pushdown）和维护信息（Pushup）。

对于打标记，当一个节点被打上区间 b 加上 x 的标记的时候，只要把 {b\mathrm{max}} 和 \mathrm{ans} 都加上 x 即可。

那么最重要的问题仍然是维护信息（Pushup），仍然是写出类似函数 \mathrm{calc}(i, pre) 的伪代码：

\displaystyle \begin{array}{l} \textbf{def: } \mathrm{calc}(i, pre) \\ \qquad \textbf{if } (i \text{ is a leaf node}) \\ \qquad \qquad \textbf{return } {\color{green}{{a\mathrm{min}}[i] + \max \{ pre, {b\mathrm{max}}[i] \} }} \\ \qquad \textbf{else} \\ \qquad \qquad \textbf{if } ({b\mathrm{max}}[\mathrm{leftchild}[i]] > pre) \\ \qquad \qquad \qquad \textbf{return } \min \{ {\color{blue}{\mathrm{calc}(\mathrm{leftchild}[i], pre)}}, {\color{red}{\mathrm{ans}[i]}} \} \\ \qquad \qquad \textbf{else} \\ \qquad \qquad \qquad \textbf{return } \min \{ {\color{blue}{{a\mathrm{min}}[\mathrm{leftchild}[i]] + pre}}, {\color{red}{\mathrm{calc}(\mathrm{rightchild}[i], pre)}} \} \\ \qquad \qquad \textbf{endif.} \\ \qquad \textbf{endif.} \\ \textbf{enddef.} \end{array}

对于当前节点 i 是叶节点的情况显然。
假如 pre < {b\mathrm{max}}[\mathrm{leftchild}[i]]，那么对右子树来说直接继承答案即可，然后递归进左子树。
否则左子树中所有的 b_i 都 \le pre，那么 b 的前缀 \max 也自然是都等于 pre，只要考虑 a_i 的最小值即可。

最后需要求整个数组中满足 c_i \le k 的最大下标 i，一般情况下可以直接线段树上二分，但是这里比较特殊。

考虑一个新函数 \mathrm{solve}(i, pre)，表示当前缀最大值为 pre 时，线段树中节点 i 对应的区间 c_i \le k 的最大下标 i。

  1. 如果 {b\mathrm{max}}[\mathrm{leftchild}[i]] > pre，也就是说 pre 影响不到右子树：
    那么，如果 \mathrm{ans}[i] \le k，就递归进右子树，否则递归进左子树。
    复杂度显然是 \mathcal O (\log n)。
  2. 如果 {b\mathrm{max}}[\mathrm{leftchild}[i]] \le pre，也就是说左子树完全被 pre 控制了：
    先递归进右子树查询，如果没查询到，则考虑左子树因为被 pre 控制了，限制变为 a_i + pre \le k。
    则移项得到 a_i \le k - pre，在左子树内是一个正常的线段树上二分的子问题（需要新写一个函数查询）。
    因为只会进行 \mathcal O (\log n) 次线段树上二分，所以时间复杂度为 \mathcal O (\log^2 n)。

至此我们在 \mathcal O (n \log^2 n) 的时间复杂度内解决了这个问题。