区间加，区间修改，求区间最大值/历史最大值。
\(n, T \le 10^5\)
好久没有紫题让我卡 \(4h\)，跨一天才写出来的紫题了。刷新了我对懒标记的认知。
考虑如果没有求历史最大值这个事情，还是比较简单的，打 f, to, add 的赋值和加的 \(tag\) 即可（\(f\) 是是否有赋值操作），合并 \(tag\) 也相当容易。
但有了查历史最大值，事情就没有那么简单了。我们要记录信息：mx, hmx 表示当前最大值以及历史最大值，pushup 很好搞定。关键在于懒标记，可能需要记录 \(5\) 个：f, to, add, mxto, mxadd 表示是否有赋值操作，赋值成为了什么，加了多少，以及历史的中的最大区间赋值以及最大区间加。
然后发现这还不好合并，因为懒标记实际上对应的是一个操作序列，懒标记合并操作相当于将下传的懒标记序列添加到原有懒标记序列后面。如果出现 “赋值， 加，赋值，加， 赋值，.....” 之类的情况，每个赋值操作都要对应一个最大的加，用一个变量显然是无法记录的。
解决方式是，对于一个懒标记来说，只要有了赋值操作，后面的操作都可以看成赋值操作，比如说对于 \([l, r]\) 先赋值为 \(v\)，再区间加 \(k\)，相当于先赋值成 \(v\)，再赋值为 \(v + k\)。这样一个懒标记可以分成前后两部分，前面是加法，后面是赋值。这样合并起来就比较舒服了。具体见代码。
实现时可以单开一个结构体表示懒标记，比较清晰。
struct Tag { // 懒标记bool f;int to, add, mxto, mxadd; // 如上述含义
};struct SegTree {int mx, hmx;Tag t;
} tr[MAXN * 4]; int n, T, a[MAXN];void update(int x, Tag &t) {if (!tr[x].t.f) { // 只有原有懒标记序列全是加法，才可以。而 (加 + 赋) + 加，两个加是不可以合并的。tr[x].t.mxadd = max(tr[x].t.mxadd, tr[x].t.add + t.mxadd);tr[x].t.add += t.add;}if (t.f) { // 赋值操作tr[x].t.mxto = max({tr[x].t.mxto, tr[x].t.to + t.mxadd, t.mxto}); // 加 + 赋 + 加 + 赋tr[x].t.to = t.to, tr[x].hmx = max({tr[x].mx + t.mxadd, tr[x].hmx, t.mxto});tr[x].mx = t.to, tr[x].t.f = 1;} else {tr[x].hmx = max(tr[x].hmx, tr[x].mx + t.mxadd), tr[x].mx += t.add;if (tr[x].t.f) { // 将 赋值 + 加 操作变成赋值操作tr[x].t.mxto = max(tr[x].t.mxto, tr[x].t.to + t.mxadd);tr[x].t.to += t.add;}}
}
懒标记实际对应的是一个序列，如何将连个懒标记序列合并是 pushdown 的关键，需要具体问题具体分析。没怎么见过可能脑子会变成一坨浆糊。