题意回顾

• 环形密码盘，$n$ 格，每格一个数字 $A_i \in [0,9]$ 和一个运算符 $C_i \in \{+,*\}$。
• 解密：从起点 $pos$ 开始，生成数组 $B$：
  • $B_0 = A_{pos}$
  • $B_x = \begin{cases} (A_{(pos+x)\bmod n} + B_{x-1}) \bmod 10, & C_{(pos+x)\bmod n} = '+' \\ (A_{(pos+x)\bmod n} \times B_{x-1}) \bmod 10, & C_{(pos+x)\bmod n} = '*' \end{cases}$
• 将 $B$ 视为环，找最远的零区间（连续 $0$ 段）。
• 距离：零区间中任意 $0$ 到 $B_0$ 的环上最短距离的最小值。
• 操作：修改某格数字和运算符，或询问从某点开始的解密结果。

数据范围：$n, m \leq 10^5$。

---

核心思路

1. 函数复合视角

每个位置的运算可以看作一个函数 $f_i: \mathbb{Z}_{10} \to \mathbb{Z}_{10}$：

• 若 $C_i = '+'$，则 $f_i(x) = (x + A_i) \bmod 10$
• 若 $C_i = '*'$，则 $f_i(x) = (x \times A_i) \bmod 10$

解密过程就是函数复合： $ B_k = f_{pos+k} \circ f_{pos+k-1} \circ \cdots \circ f_{pos+1}(A_{pos}) $

---

2. 仿射变换与复合

实际上，这两种运算在模 $10$ 下构成仿射变换： $f(x) = (m \cdot x + a) \bmod 10$

• 对于加法：$m=1, a=A_i$
• 对于乘法：$m=A_i, a=0$

复合规则：
设 $F_1(x) = (m_1 x + a_1) \bmod 10$，$F_2(x) = (m_2 x + a_2) \bmod 10$，则： $ F_2 \circ F_1(x) = m_2(m_1 x + a_1) + a_2 = (m_2 m_1) x + (m_2 a_1 + a_2) \bmod 10 $ 即新函数参数为： $ m' = m_2 m_1 \bmod 10,\quad a' = (m_2 a_1 + a_2) \bmod 10 $

---

3. 线段树维护

用线段树维护任意区间 $[l, r]$ 的复合函数 $(m_{l,r}, a_{l,r})$。

建树：
叶子 $i$：若 $C_i = '+'$，则 $(1, A_i)$；若 $C_i = '*'$，则 $(A_i, 0)$。

合并：
对于节点 $[l, r]$，设左子 $[l, mid]$ 为 $(m_L, a_L)$，右子 $[mid+1, r]$ 为 $(m_R, a_R)$，则： $ m = m_R \cdot m_L \bmod 10,\quad a = (m_R \cdot a_L + a_R) \bmod 10 $

修改：$O(\log n)$ 更新叶子并上推。

---

4. 零区间判定

从起点 $pos$ 开始，$B_0 = A_{pos}$。
$B_k$ 是前 $k$ 步复合函数作用在 $A_{pos}$ 上的结果： $ B_k = m_{1..k} \cdot A_{pos} + a_{1..k} \pmod{10} $ 其中 $(m_{1..k}, a_{1..k})$ 是区间 $[pos+1, pos+k]$ 的复合函数（环状处理）。

因此： $ B_k = 0 \iff m_{1..k} \cdot A_{pos} + a_{1..k} \equiv 0 \pmod{10} $

---

5. 环上最远零区间查找

距离定义：在长度为 $n$ 的环上，位置 $k$ 到位置 $0$ 的距离为： $\text{dist}(k) = \min(k, n-k)$ 零区间 $[L, R]$ 的距离为 $\min\limits_{k \in [L,R]} \text{dist}(k)$。

查找策略：

1. 找出所有满足 $B_k = 0$ 的 $k$（即满足同余条件的 $k$）
2. 将这些 $k$ 按环上位置排序，找出所有连续零区间
3. 对每个零区间计算其到 $0$ 的距离，取最大值

不需要检查所有 $k$，只需在可能成为最远零区间的候选位置检查。

---

算法流程

初始化

• 读入 $n, m$ 和密码盘数据
• 建线段树

修改操作

• 更新叶子节点的 $(m, a)$
• 上推合并

询问操作

1. 从起点 $pos$ 开始，$B_0 = A[pos]$
2. 如果 $B_0 = 0$，则包含 $B_0$ 的零区间距离为 $0$
3. 计算环上对面区域（距离 $\approx n/2$）的复合函数
4. 二分查找该区域附近的零区间
5. 检查 $B_0$ 附近的零区间
6. 取所有零区间距离的最大值
7. 如果没有零区间，输出 $-1$

---

复杂度分析

• 建树：$O(n)$
• 修改：$O(\log n)$
• 询问：$O(\log^2 n)$（二分查找 + 线段树查询）
• 总复杂度：$O(n + m \log^2 n)$，可过 $10^5$

---

总结

1. 函数复合：将递推转化为仿射变换复合
2. 线段树：$O(\log n)$ 查询任意区间复合函数
3. 模运算性质：利用模 $10$ 简化计算
4. 环上二分：在关键区域查找最远零区间

通过数学转化与数据结构结合，将朴素 $O(nm)$ 优化到 $O(m \log^2 n)$，解决了大数据范围的问题。