[SCOI2015] 小凸解密码
题目描述
小凸得到了一个密码盘,密码盘被等分成 $n$ 个扇形,每个扇形上有一个数字 $(0 \sim 9)$,和一个符号 $($ `+` 或 `*` $)$。密码盘解密的方法如下:
首先,选择一个位置开始,顺时针地将数字和符号分别记在数组 $A$ 和数组 $C$ 中。解密的方法如下:
- $B_0 = A_0$
- 当 $x > 0$ 时:
- 若 $C_x$ 为 `+`,$B_x = (A_x + A_{x - 1}) \% 10$
- 若 $C_x$ 为 `*`,$B_x = (A_x \times A_{x - 1}) \% 10$
操作完成后,可以得到一个长度为 $n$ 的数组 $B$,然后以 $B_0$ 为起点将 $B$ 数组顺时针写成一个环,解密就完成了,称得到的环为答案环。
现在小凸得到了一份指令表,指令表上有 2 种操作。一种指令是修改操作,即改变原来密码盘上一个位置的数字和符号。另一种指令是询问操作,具体如下:
- 首先从指令给出的位置开始完成解密,得到答案环。
- 答案环上会有一些 $0$ 连在一起,将这些连在一起的 $0$ 称为零区间,找出其中距离 $B_0$ 最远的那个零区间,输出这个距离(零区间和 $B_0$ 的距离定义为:零区间内所有 $0$ 到 $B_0$ 距离中的最小值)。
输入输出格式
输入格式
第一行包含两个整数 $n, m$,代表密码盘大小和指令个数。
接下来 $n$ 行,每行包含一个整数和一个字符,按顺时针顺序给出了密码盘上的数组和符号。
接下来 $m$ 行,依次给出指令。每行第一个整数代表指令类型:
- 若第一个整数为 `1`,代表本行对应指令为修改操作,之后依次有两个整数 $pos, num$ 和一个字符 $\rm opt$,分别代表修改的位置,以及修改后该位置的数字和字符。
- 若第一个整数为 `2`,代表本行对应指令位询问操作,之后有一个整数 $pos$,代表本次操作中解密的开始位置。
密码盘上的位置标号为 $0$ 到 $n - 1$。
数据保证合法,即数据中 $0 \leq pos < n, 0 \leq num \leq 9$,$\rm opt$ 为 `+` 或 `*`。
输出格式
对于每个询问操作 $1$ 行,输出答案,若答案环上没有 $0$,输出 `−1`。
输入输出样例
输入样例 #1
5 8
0 *
0 *
0 *
0 *
0 *
2 0
1 0 1 +
1 2 1 +
2 3
1 1 1 +
1 3 1 +
1 4 1 +
2 4
输出样例 #1
0
2
-1
说明
**样例解释:**
对于第 $1$ 个询问,答案环为 $\{0, 0, 0, 0, 0\}$,仅有 $1$ 个零区间,且 $B_0$ 在其中,所以距离是 $0$。
对于第 $2$ 个询问,答案环为 $\{0, 0, 1, 0, 1\}$,有 $2$ 个零区间,$[0, 1]$ 和 $B_0$ 距离是 $0$,$[3, 3]$ 和 $B_0$ 距离是 $2$,故答案为 $2$。
对于第 $3$ 个询问,答案环为 $\{1, 2, 2, 2, 2\}$,没有零区间,答案是 `−1`。
**数据范围:**
对于 $20 \%$ 数据,$5 \leq n \leq 10^5, 5 \leq m \leq 1000$;
对于 $60 \%$ 数据,$5 \leq n \leq 10^5, 5 \leq m \leq 10^4$;
对于 $100 \%$ 数据,$5 \leq n, m \leq 10^5$。