本来想写点技巧，但感觉这个东西就只能拿复合函数分析一下或者矩阵分析，所以这玩意感觉真没啥技巧。
注：不建议作为学习文章，仅为个人的整理笔记。
突然发现这种双半群信息维护用线段树貌似常数很大，出题人会把时间和数据范围开的很松。如果码力智商不够可以考虑更易理解且有时候更好写的分块做法。
CatOJ C0335C 求和
很容易想到差分然后离线下来扫描线，把 \(l_1,r_1\) 分别挂到 \(l_2-1\) 和 \(r_2\) 上。可以分别维护 \(\min/\max\)。以 \(\max\) 为例，维护 \(s_i\) 表示当前扫到 \(r\) 时，\([i,r]\) 的 \(\max\) 值。询问时相当于是求 \([l_1,r_1]\) 的历史版本和。那么如何维护历史版本和呢？
一个经典的做法就是维护当前点 \(i\) 上一次修改时的时间 \(t\)，以及时间在 \(t\) 之前的所有时间的历史版本和 \(v\)，还有当前时间的值 \(s\)。对于 \(T\) 时间的一次询问区间历史版本和，可以转化成查询 \(\sum v+T\sum s -\sum st\)。直接线段树维护就可以。
炫酷做法：由于本题 \(10^5\)，所以可以考虑拍个分块上去，每次时间往后推一次时整块加整块即可。
对于 \(r\leftarrow r+1\) 时的修改，拍个单调栈边弹出边修改即可。总时间复杂度是 \(\mathcal O((n+q)\log n)\) 的。
[NOIP2022] 比赛
扫描方式跟上一道题类似，只不过现在是要你维护两个数组的乘积 \(\max\)。
考虑分析需要维护哪些 tag。设 \(s\) 为 \(ab\) 的历史版本和，普通的是这种形式：
对于 \(a\) 数组的区间加 \(f(a,b,s)\leftarrow f(a + \Delta a,b,s+(a+\Delta a)b)\)，\(b\) 数组的区间加 \(f(a,b,s)\leftarrow f(a,b+\Delta b,s+(b+\Delta b)a)\)。那合并标记时就是这种形式：\(f(a,b,s)\leftarrow f(a+\Delta a,b+\Delta b,s+(a+\Delta a)(b+\Delta b))\)。对于本题里我们写区间覆盖是同理的，\(s\) 的修改是这种式子的形式：\(s'\leftarrow s+tag_aa+tag_bb+tag_{ab}ab+tag_{x}\)，然后你还要维护 \(tag_{a'},tag_{b'}\) 表示 \(a,b\) 被覆盖的值。还有一个问题是标记合并是很抽象的，不好理解，可以把标记写成矩阵的形式，具体看 这篇题解，讲的很详细。
细节特别多，光这题的历史版本和维护就困扰了我大半年，很恶心，感觉场切的都好神仙。时间复杂度还是 \(\mathcal O((n+q)\log n)\)，如果不想手动实现标记合并可以直接写矩乘，理论复杂度是 \(\mathcal O(5^3(n+q)\log n)\)，手动实现一小部分为 \(0\) 的元素乘要快很多。
炫酷做法：考虑分块，打标记方法跟线段树一样。优化的地方在于，线段树标记合并是一个由层数将标记向上合并的一个过程，标记会随着层数的增加而复杂。而分块只需要对于单个整块合并没有经过合并的新标记与原先的标记。也就是说，线段树的标记合并是多层与多层合并的，分块的标记合并是单层与多层合并的，更好写常数也更小。时间复杂度 \(\mathcal O((n+q)\sqrt n)\)。
[THUSCH2017] 大魔法师
感谢坤皇的推题。
这题用矩阵分析特别地简单，但是题解里面感觉都是在硬套矩阵乘法的框架，都没有提到标记的原理，我还是来提几嘴。
你显然是要分别对于每个 \(a,b,c\)，都要维护 \(tag_a,tag_b,tag_c,tag_x\)，举个例子就是 \(a'\leftarrow tag_aa+tag_bb+tag_cc+tag_x\)。你显然会有 \(16\) 个标记，标记合并时模拟矩阵乘法相乘即可。
时间复杂度 \(\mathcal O(q\log n)\)。
炫酷做法：分块，标记跟线段树维护的一样，但是仍然是单层对多层，\(\mathcal O(q\sqrt n)\) 5s 轻松通过。
因为感觉每次做完这种题都晕晕的，所以写了一篇文章记录一下，如果后面遇到类似的题会继续更新。
其实有好的题也可以推给我。qwq