# 复合摘要：字符计数、质因子集合与代数 Lazy

## 本节目标

学会从查询公式反推节点摘要，把多个可合并量组成乘积幺半群，并推导区间乘法对“乘积 + 质因子集合”的 Lazy 作用。

## 前置知识与课前自测

前置：Lazy Segment Tree、快速幂、Euler $φ$ 公式、位掩码。

1. 区间字符串排序真正需要保存字符顺序吗？
2. $\varphi(N)$ 除了 $N$ 本身，还需要知道什么？
3. 区间每个数乘 $x$ 时，区间乘积怎样变化？

<details><summary>答案</summary>

1. 不需要，只需 26 个字符频数，排序后顺序由频数唯一决定。
2. $N$ 的不同质因子集合。
3. 长度为 len 的区间乘积乘上 $x^{len}$。

</details>

## 问题动机与核心知识

线段树不是只能保存一个数。只要摘要能结合、修改能作用于摘要并可组合 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](https://vjudge.net/problem/CodeForces-558E)，难度 2300
- $n\le10^5,q\le5\times10^4$；每次把子串升序或降序排序，输出最终串。

<details><summary>Hint 1</summary>查询区间 26 个字符频数。</details>
<details><summary>Hint 2</summary>按目标方向把连续字符段依次覆盖回区间。</details>

### Observations

- 排序结果只由频数决定，原区间内部位置关系全部被丢弃。
- 一次操作最多写 26 个常值段，与区间长度无关。
- 节点摘要为 26 维计数；常值赋值 Lazy 可直接重置摘要。

### Editorial 与正确性证明

线段树每节点存各字符数，Lazy 表示整段被赋成某字符。查询得到 $cnt[c]$ 后，从左端开始按升/降字符顺序，把长度 `cnt[c]` 的连续段赋为 c。所有段总长等于原区间长且互不重叠；字符多重集不变、排列单调，因此恰是排序结果。每次 $O(26\log n)$。

### 核心伪代码与附件

```text
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]
```

[完整 C++17 附件](../../参考实现/08-高级线段树与树状数组/CodeForces-558E.cpp)

## 精选例题 2：Please, another Queries on Array?

### 来源与题意

- [CodeForces-1114F Please, another Queries on Array?](https://vjudge.net/problem/CodeForces-1114F)，难度 2400
- $n\le4\times10^5,q\le2\times10^5$，初值和乘数均 $1..300$；区间乘，查询区间乘积的 Euler $φ$ 值模 $10^9+7$。

<details><summary>Hint 1</summary>$\varphi(N)=N\prod_{p\mid N}(p-1)/p$。</details>
<details><summary>Hint 2</summary>节点保存区间乘积与出现过的质因子 OR 掩码。</details>
<details><summary>Hint 3</summary>区间乘 x：乘积乘 $x^{len}$，掩码 OR `mask[x]`。</details>

### 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)$。

### 核心伪代码与附件

```text
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)
```

[完整 C++17 附件](../../参考实现/08-高级线段树与树状数组/CodeForces-1114F.cpp)

## 灵活性实验室

[CodeForces-1172F Nauuo and Bug](https://vjudge.net/problem/CodeForces-1172F)（3300）把一段数组视为对输入累加器的函数，并在线段树节点合成函数摘要，回答区间函数作用。它训练“线段树维护函数而非数值”；仅部分相关，不作为后续前置。

## 扩展与联系

把节点摘要与 Lazy 看成代数对象，能系统判断模板是否可用：摘要需有结合合并，标记需可复合，并满足标记对合并的作用一致性。矩阵、仿射函数、括号信息都可按同一视角设计。

## 总结与自检

1. 字符排序为什么只需频数？
2. Euler $φ$ 为什么只需不同质因子集合？
3. 区间乘对乘积的指数为何是区间长度？
4. 两部分 Lazy 的单位元和复合分别是什么？

## 课后训练建议

先用纸面写出摘要/合并/作用/复合四张表，再编码。随机对拍时让乘数含多个质因子、重复质因子和 1，检查 OR 与指数更新边界。