半群
幺半群同态一个示例的双向分析
全体自然数（含 0）在加法下构成一个幺半群，记作 (N, +)，而全体正整数在乘法下也构成一个幺半群，记作 (Z+, ·). 假设映射 f: N→ Z+ 满足 ① ∀ x, y ∈ N, f(x + y) = f(x)·f(y). 令 y = 0，代入 ① 有 f(x) = f(x)·f(0)，由此 ......
搬运的 对于维护双半群信息以及扫描线问题的整理？
本来想写点技巧，但感觉这个东西就只能拿复合函数分析一下或者矩阵分析，所以这玩意感觉真没啥技巧。 注：不建议作为学习文章，仅为个人的整理笔记。 突然发现这种双半群信息维护用线段树貌似常数很大，出题人会把时间和数据范围开的很松。如果码力智商不够可以考虑更易理解且有时候更好写的分块做法。 CatOJ C0 ......
区间半群查询与 Ackermann 函数
最近在思考半在线卷积的复杂度有没有可能进一步优化, 决定先理清类似的问题以寻求经验. ## 一区间合并 如果询问的时候不能进行半群运算, 显然我们需要在预处理阶段处理所有答案, 必须进行 $O(n^2)$ 次计算. ## 二区间合并 如果询问的时候可以进行一次半群运算, 则可以把序列每次在中点处折开 ......