306800: CF1252K. Addition Robot
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Addition Robot
题意翻译
给出一个长度为 $N$,只含有大写字母 A 和 B 的字符串 $S=S_1S_2S_3...S_n$,定义如下函数 $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) ``` 给出初始字符串 $S$,你需要执行以下 $Q$ 次操作: `1 L R`:将 $S_L,S_{L+1},...,S_{R-1},S_r$ 取反(A 变为 B,B 变为 A)。 `2 L R A B`:输出函数调用 $F(L,R,A,B)$ 的结果,对 $10^9+7$ 取模。 $1\le N,Q\le 10^5$题目描述
Adding two numbers several times is a time-consuming task, so you want to build a robot. The robot should have a string $ S = S_1 S_2 \dots S_N $ of $ N $ characters on its memory that represents addition instructions. Each character of the string, $ S_i $ , is either 'A' or 'B'. You want to be able to give $ Q $ commands to the robot, each command is either of the following types: - 1 $ L $ $ R $ . The robot should toggle all the characters of $ S_i $ where $ L \le i \le R $ . Toggling a character means changing it to 'A' if it was previously 'B', or changing it to 'B' if it was previously 'A'. - 2 $ L $ $ R $ $ A $ $ B $ . The robot should call $ f(L, R, A, B) $ and return two integers as defined in the following pseudocode: ``` <pre class="lstlisting">``` function f(L, R, A, B):<br></br> FOR i from L to R<br></br> if S[i] = 'A'<br></br> A = A + B<br></br> else<br></br> B = A + B<br></br> return (A, B)<br></br> ``` ``` You want to implement the robot's expected behavior.输入输出格式
输入格式
Input begins with a line containing two integers: $ N $ $ Q $ ( $ 1 \le N, Q \le 100\,000 $ ) representing the number of characters in the robot's memory and the number of commands, respectively. The next line contains a string $ S $ containing $ N $ characters (each either 'A' or 'B') representing the initial string in the robot's memory. The next $ Q $ lines each contains a command of the following types. - 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 $ ) There is at least one command of the second type.
输出格式
For each command of the second type in the same order as input, output in a line two integers (separated by a single space), the value of $ A $ and $ B $ returned by $ f(L, R, A, B) $ , respectively. As this output can be large, you need to modulo the output by $ 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