← 返回题目列表

AtCoder · abc434_g

G. 键盘

中文机器翻译题面 查看原题

分数: 650 点

问题陈述

对于字符串 A 组成 1, 2, \dots, 9 和 B,定义 f(A) 为通过以下过程获得的字符串:

  • 最初有一个空字符串 C.
  • 按顺序执行以下操作 i = 1, 2, \dots, |A|:
    • If A_i 是其中之一 1, 2, \dots, 9,追加 A_i 到年底 C.
    • If A_i = B,删除最后一个字符 C。然而,如果 C 是一个空字符串,不执行任何操作。
  • 让 f(A) be C 完成以上所有操作后。

给你一个字符串 S 长度 N 组成 1, 2, \dots, 9,和 B.
流程 Q 查询如下所述。每个查询属于以下两种类型之一:

  • 1\ \ x\ \ c :更新 S_x to c。 (这里, c is 1, 2, \dots, 9,或 B.)
  • 2\ \ l\ \ r :让 T 是通过提取形成的字符串 l-th 通过 r第一个字符 S。然后,让 U=f(T)。如果 U 为空字符串,输出 -1;否则,输出当值为 U 视为十进制整数除以 998244353.

约束

  • 1 \leq N \leq 8 \times 10^6
  • 1 \leq Q \leq 2 \times 10^5
  • S 是一个长度为的字符串 N 组成 1, 2, \dots, 9,和 B.
  • 1 \leq x \leq N
  • c is 1, 2, \dots, 9,或 B.
  • 1 \leq l \leq r \leq N
  • N, Q, x, l, r 是整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{query}_i 表示 i第一个查询。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均以以下两种格式之一给出:

1 x c
2 l r

输出

按照问题陈述中的说明输出由换行符分隔的查询的答案。


示例输入 1

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

示例输出 1

567
2345678
236323538
-1
5678
567891
589
125891

对于第一个查询, T=U= 567。因此,输出 567.
对于第三个查询, T=U= 1234567891。因此,输出 1234567891 \bmod 998244353 = 236323538.
对于第六个查询, T= 2BB 和 U 是一个空字符串。因此,输出 -1.