05-复合摘要与代数标记.md 5.7 KB
复合摘要：字符计数、质因子集合与代数 Lazy
本节目标
学会从查询公式反推节点摘要，把多个可合并量组成乘积幺半群，并推导区间乘法对“乘积 + 质因子集合”的 Lazy 作用。
前置知识与课前自测
前置：Lazy Segment Tree、快速幂、Euler $φ$ 公式、位掩码。
- 区间字符串排序真正需要保存字符顺序吗？
- $\varphi(N)$ 除了 $N$ 本身，还需要知道什么？
- 区间每个数乘 $x$ 时，区间乘积怎样变化？
答案
1. 不需要，只需 26 个字符频数，排序后顺序由频数唯一决定。 2. $N$ 的不同质因子集合。 3. 长度为 len 的区间乘积乘上 $x^{len}$。问题动机与核心知识
线段树不是只能保存一个数。只要摘要能结合、修改能作用于摘要并可组合 Lazy，就能维护：
$$ summary=(product\bmod M,\ primeMask), $$
合并是 (乘法, OR)；乘 $x$ 的标记是 (x,mask(x))，作用为 product*=x^len, mask|=mask(x)，标记复合仍是 (乘法, OR)。
这种推导方式比“给模板加数组”可靠：先写摘要语义、合并律、标记作用、标记复合，再编码。
实现指南
- $1..300$ 只有 62 个质数，可放进
uint64_t；若质数更多应换动态 bitset。 - 标记的乘法单位元是 1，集合单位元是 0。
- 查询返回的临时摘要也要使用同一合并律。
- 字符排序区间的重写片段必须无缝覆盖原区间，否则旧字符残留。
精选例题 1：A Simple Task
来源与题意
- CodeForces-558E A Simple Task，难度 2300
- $n\le10^5,q\le5\times10^4$；每次把子串升序或降序排序，输出最终串。
Hint 1
查询区间 26 个字符频数。Hint 2
按目标方向把连续字符段依次覆盖回区间。Observations
- 排序结果只由频数决定，原区间内部位置关系全部被丢弃。
- 一次操作最多写 26 个常值段，与区间长度无关。
- 节点摘要为 26 维计数；常值赋值 Lazy 可直接重置摘要。
Editorial 与正确性证明
线段树每节点存各字符数，Lazy 表示整段被赋成某字符。查询得到 $cnt[c]$ 后，从左端开始按升/降字符顺序，把长度 cnt[c] 的连续段赋为 c。所有段总长等于原区间长且互不重叠；字符多重集不变、排列单调，因此恰是排序结果。每次 $O(26\log n)$。
核心伪代码与附件
counts = query_character_counts(l, r)
position = l
for c in alphabet_order(chosen_direction):
if counts[c] > 0:
range_assign(position, position+counts[c]-1, c)
position += counts[c]
精选例题 2：Please, another Queries on Array?
来源与题意
- CodeForces-1114F Please, another Queries on Array?，难度 2400
- $n\le4\times10^5,q\le2\times10^5$，初值和乘数均 $1..300$；区间乘，查询区间乘积的 Euler $φ$ 值模 $10^9+7$。
Hint 1
$\varphi(N)=N\prod_{p\mid N}(p-1)/p$。Hint 2
节点保存区间乘积与出现过的质因子 OR 掩码。Hint 3
区间乘 x：乘积乘 $x^{len}$，掩码 OR `mask[x]`。Observations
- 不需要质因子指数；它们已经包含在区间乘积 $N$ 中，$φ$ 的修正项每种质数只乘一次。
- 限制
x<=300把质数宇宙压到 62 位，这是题目给出的关键可实现信号。 - 乘法标记按乘法组合，质因子标记按 OR 组合，两部分互不干扰但必须同步下传。
Editorial
预处理每个 $x\le300$ 的质因子掩码和每个质数的模逆。线段树合并区间乘积与掩码。查询后从 product 出发，对掩码每个质数乘 $(p-1)p^{-1}$。
正确性证明
节点乘积由模乘结合律正确合并；掩码 OR 恰表示左右区间质因子并集。区间乘操作对每个元素乘 x，所以总乘积恰乘 $x^{len}$，新增质因子恰为 mask[x]。归纳得查询摘要等于真实区间；Euler 乘积公式随后给出答案。每次 $O((\log n)+62)$。
核心伪代码与附件
summary = (product_mod, prime_mask)
combine(A,B) = (A.product*B.product mod MOD, A.mask OR B.mask)
apply_multiply(node, x):
node.product *= pow(x, node.length)
node.mask |= factor_mask[x]
query_phi(l,r):
product, mask = query(l,r)
for each prime bit in mask: product *= (p-1) * inverse(p)
灵活性实验室
CodeForces-1172F Nauuo and Bug（3300）把一段数组视为对输入累加器的函数，并在线段树节点合成函数摘要，回答区间函数作用。它训练“线段树维护函数而非数值”；仅部分相关，不作为后续前置。
扩展与联系
把节点摘要与 Lazy 看成代数对象，能系统判断模板是否可用：摘要需有结合合并，标记需可复合，并满足标记对合并的作用一致性。矩阵、仿射函数、括号信息都可按同一视角设计。
总结与自检
- 字符排序为什么只需频数？
- Euler $φ$ 为什么只需不同质因子集合？
- 区间乘对乘积的指数为何是区间长度？
- 两部分 Lazy 的单位元和复合分别是什么？
课后训练建议
先用纸面写出摘要/合并/作用/复合四张表，再编码。随机对拍时让乘数含多个质因子、重复质因子和 1，检查 OR 与指数更新边界。