ABC 434 G

· · 个人记录

题目描述：

对于一个由字符 1, 2, …, 9 和 B 组成的字符串 A，定义函数 f(A) 为通过以下过程得到的字符串：

初始时，设 C 为一个空字符串。

按顺序处理 A 中的每个字符（i = 1, 2, …, |A|）：

如果当前字符 A_i 是 1 到 9 之间的某个数字，则将该字符添加到 C 的末尾。

如果当前字符 A_i 是 B，则删除 C 的最后一个字符。但如果 C 为空字符串，则不进行任何操作。

完成所有上述操作后，将最终的 C 定义为 f(A)。

现给定一个长度为 N 的字符串 S，由 1, 2, …, 9 和 B 组成。 需要处理 Q 个查询，每个查询为以下两种类型之一：

更新操作：1 x c

将 S 中第 x 个字符更新为 c。（其中 c 是 1, 2, …, 9 或 B。）

询问操作：2 l r

令 T 为从 S 中提取第 l 到第 r 个字符形成的子串。

计算 U = f(T)。

如果 U 是空字符串，输出 -1；否则，将 U 视为一个十进制整数，输出该整数除以 998244353 的余数。

约束条件：

1 ≤ N ≤ 8 × 10^6

1 ≤ Q ≤ 2 × 10^5

S 是长度为 N 的字符串，仅包含 1, 2, …, 9 和 B。

1 ≤ x ≤ N

c 是 1, 2, …, 9 或 B。

1 ≤ l ≤ r ≤ N

所有输入值（N, Q, x, l, r）均为整数。

输入格式：

第一行：N 和 Q

第二行：字符串 S

接下来 Q 行：每行一个查询，格式为 1 x c 或 2 l r

输出格式：

对于每个类型 2 的查询，按题目要求输出一行答案。

10 12
1234567891
2 5 7
2 2 8
2 1 10
1 3 B
1 4 B
2 2 4
2 2 8
2 1 10
1 7 B
2 3 9
1 3 4
2 1 10

567
2345678
236323538
-1
5678
567891
589
125891

注意： 在第一个样例查询中，T = U = "567"，因此输出 567。

在第三个样例查询中，T = U = "1234567891"，输出 1234567891 mod 998244353 = 236323538。

在第六个样例查询中，T = "2BB"，U 为空字符串，因此输出 -1。

题解：https://atcoder.jp/contests/abc434/editorial/14687