← 返回题目列表

Codeforces · 1252/K

K. 加法机器人

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

多次将两个数字相加是一项耗时的任务,因此您想构建一个机器人。机器人的内存中应该有一个字符串 $$$S = S_1 S_2 \dots S_N$$$,包含 $$$N$$$ 个字符,表示加法指令。字符串 $$$S_i$$$ 的每个字符都是“A”或“B”。

您希望能够向机器人发出 $$$Q$$$ 命令,每个命令都是以下类型之一:

- 1 $$$L$$$ $$$R$$$。机器人应该切换 $$$S_i$$$ 的所有字符,其中 $$$L \le i \le R$$$。切换字符意味着如果之前是“B”,则将其更改为“A”;如果之前是“A”,则将其更改为“B”。
- 2 $$$L$$$ $$$R$$$ $$$A$$$ $$$B$$$。机器人应调用 $$$f(L, R, A, B)$$$ 并返回两个整数,如以下伪代码中所定义: function f(L, R, A, B): FOR i from L to R if S[i] = 'A' A = A + B else B = A + B return (A, B)

您想要实现机器人的预期行为。

输入

输入以包含两个整数的行开头: $$$N$$$ $$$Q$$$ ($$$1 \le N, Q \le 100\,000$$$) 分别表示机器人内存中的字符数和命令数。下一行包含一个字符串 $$$S$$$,其中包含 $$$N$$$ 字符(每个字符为“A”或“B”),表示机器人内存中的初始字符串。接下来的 $$$Q$$$ 行每行包含以下类型的命令。

- 1 $$$L$$$ $$$R$$$ ($$$1 \le L \le R \le N$$$)
- 2 $$$L$$$ $$$R$$$ $$$A$$$ $$$B$$$ ($$$1 \le L \le R \le N$$$; $$$0 \le A, B \le 10^9$$$)

输出

对于第二类命令,按照与输入相同的顺序,一行输出两个整数(用一个空格分隔),分别为$$$f(L, R, A, B)$$$返回的$$$A$$$和$$$B$$$的值。由于此输出可能很大,因此您需要对输出取模 $$$1\,000\,000\,007$$$。

示例

输入 #1

5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000

输出 #1

11 3
0 1000000000

注意

示例输入/输出 #1 的说明

对于第一个命令,调用 $$$f(L, R, A, B)$$$ 会导致以下结果:

- 最初,$$$A = 1$$$ 且 $$$B = 1$$$。
- 在 $$$i = 1$$$ 末尾,$$$A = 2$$$ 和 $$$B = 1$$$。
- 在 $$$i = 2$$$ 末尾,$$$A = 2$$$ 和 $$$B = 3$$$。
- 在 $$$i = 3$$$ 末尾,$$$A = 5$$$ 和 $$$B = 3$$$。
- 在 $$$i = 4$$$ 末尾,$$$A = 8$$$ 和 $$$B = 3$$$。
- 在 $$$i = 5$$$ 末尾,$$$A = 11$$$ 和 $$$B = 3$$$。

对于第二个命令,字符串 $$$S$$$ 将更新为“ABBBB”。

对于第三个命令,$$$A$$$ 的值将始终为 $$$0$$$,$$$B$$$ 的值将始终为 $$$1\,000\,000\,000$$$。因此,$$$f(L, R, A, B)$$$ 将返回 $$$(0, 1\,000\,000\,000)$$$。