一种可快速合并的信息

aurora5090 / 2024-12-29 / 原文

建立坐标系，$x$ 作为输入，$y$ 作为输出

假如这种系统形如：一段水平线 + 一段 $k = 1$ 的直线 + 一段水平线

那么这种结构在级联以后是可以快速合并的（E.g. 一个连续的序列，将前一个的输出作为后一个的输入）

具体来说，这个系统可以直接用两个拐点的信息来表示

struct Node { int x1, y1, x2, y2; };

int f(int x, Node a) { // 返回一个系统 a 在 x 处的输出 y
    auto [x1, y1, x2, y2] = a;
    if (x <= x1) return y1;
    if (x >= x2) return y2;
    return x - x1 + y1;
}

神奇（神秘）的是，合并后，这个系统依然可以用两个拐点表示出来！

我们只需要讨论出最终横轴上 $x$ 的位置，然后通过 $\operatorname{f()}$ 映射求出 $y$ 就可以得到最终系统

Node operator+(const Node &a, const Node &b) {
    Node res;
    res.x1 = max(a.x1, b.x1 - a.y1 + a.x1);
    res.x2 = min(a.x2, b.x2 - a.y1 + a.x1);

    res.y1 = f(f(res.x1, a), b);
    res.y2 = f(f(res.x2, a), b);

    return res;
}

如果我们需要查询一个区间的级联情况，可以用线段树（点集划分）来快速维护。
因此可以解决形如 $\min(\text{Bound}_1, val+a_i), \max(\text{Bound}_2, val+a_i)$ 作为信息 $D$，进行级联的问题

如果是 $M$ 的话则可以考虑伟大 $ \color{Black} \text{j} \color{red} \text{iry_2}$ 的 $\text{seg beats}$

例题 2023 CCPC 秦皇岛热身赛 C. Robot / 2022 CCPC 华为云计算挑战赛 1004 机器人