P1253 题解：两种懒标记，顺序不能乱

题目链接。维护一个数组，支持区间赋值、区间加和区间最大值。

这题的关键是懒标记的顺序。先看同样两步，交换顺序后的结果：

两种操作都可以写成 $f(v)=av+b$：加上 $x$ 对应 $(a,b)=(1,x)$，赋值为 $x$ 对应 $(0,x)$。乘上 0 抹掉旧值，正好表达“覆盖”。不修改则是 $(1,0)$。

标记合并就是函数复合

设旧标记为 $g(v)=a_gv+b_g$，新操作为 $f(v)=a_fv+b_f$。真正执行的顺序是先旧后新：

新赋值的 $a_f=0$，会抹掉旧标记；新加法的 $a_f=1$，只累加偏移。

也可以写成原来的行向量矩阵：

先做 $G$ 再做 $F$，行向量右边乘的是 $GF$。 用函数复合或矩阵都能推到同一个合并式，代码不必真的存四个矩阵元素。

为什么只维护最大值就够

这里 $a\in\{0,1\}$，变换单调不减，最大值直接变成 $a\cdot\max+b$。若允许乘负数，就还需要维护最小值。

代码

下面是懒标记的核心，使用非空节点。compose(newer, older) 明确表示先执行旧标记，再执行新标记。节点整段被覆盖时更新 maximum 和 lazy；下传时把同一标记作用到两个孩子，再把父标记置回 (1,0)。

#include <algorithm>

using i64 = long long;
struct Tag { i64 a = 1, b = 0; };
struct Node { i64 maximum; Tag lazy; };

Tag compose(Tag newer, Tag older) {
    return {newer.a * older.a, newer.a * older.b + newer.b};
}

void apply(Node& node, Tag tag) {
    node.maximum = tag.a * node.maximum + tag.b;
    node.lazy = compose(tag, node.lazy);
}

// 区间加 x：apply(node, {1, x});
// 区间赋值 x：apply(node, {0, x});
// 合并孩子：maximum = std::max(left.maximum, right.maximum);

线段树的建树是 $O(n)$，单次修改、查询都是 $O(\log n)$，空间 $O(n)$。