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 的查询，按题目要求输出一行答案。

CPP

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

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

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

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

文章操作