Addition Robot (Problem K, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 3 sec
Memory limit: 256MB
Author: Prabowo Djonatan

# Problem Statement

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 \ldots 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 \leq i \leq 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:

```
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)
```

You want to implement the robot’s expected behavior.

# Input

Input begins with a line containing two integers: $N$ $Q$ ($1 \leq N, Q \leq 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 contain a command of the following types:

- 1 L R ($1 \leq L \leq R \leq N$)

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

There is at least one command of the second type.

# Output

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$.

# Sample Input #1
```
5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000
```
# Sample Output #1
```
11 3
0 1000000000
```
# Explanation for the sample input/output #1

For the first command, calling $f(L, R, A, B)$ causes the following:

- Initially, $A = 1$ and $B = 1$.
- At the end of $i = 1$, $A = 2$ and $B = 1$.
- At the end of $i = 2$, $A = 2$ and $B = 3$.
- At the end of $i = 3$, $A = 5$ and $B = 3$.
- At the end of $i = 4$, $A = 8$ and $B = 3$.
- At the end of $i = 5$, $A = 11$ and $B = 3$.

Therefore, $f(L, R, A, B)$ will return $(11, 3)$.

For the second command, string $S$ will be updated to “ABBBB”.

For the third command, the value of $A$ will always be 0 and the value of $B$ will always be $1\,000\,000\,000$.  
Therefore, $f(L, R, A, B)$ will return $(0, 1\,000\,000\,000)$.


Sample inputs:
5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000

Sample outputs:
11 3
0 1000000000

# Solution Analysis
Analysis author: Prabowo Djonatan

Let the transformation matrix for characters ‘A’ and ‘B’ be 
$\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$ and 
$\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ respectively. This is because:

$$
\begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} a + b \end{bmatrix} 
\quad \text{and} \quad 
\begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} a + b \end{bmatrix}
$$

Next, we build a segment tree of size $N$, where each node is a $2 \times 2$ matrix which is the multiplication of its two children. The $i$-th leaf node is 
$\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$ if $S[i] = A$ or 
$\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ if $S[i] = B$.

To answer the query, we simply do the standard range query operation on the segment tree and obtain the transformation matrix. Multiply the initial $A$ and $B$ with this matrix will give us the answer.

To serve the toggle operation, we do update on the segment tree (with lazy propagation). If a node containing 
$\begin{bmatrix} p & q \\ r & s \end{bmatrix}$ covers the range that is to be updated, we update the node to 
$\begin{bmatrix} s & r \\ q & p \end{bmatrix}$.

We can prove the correctness of the toggle operation by induction on the length of the character. The base case of a single character can obviously be seen as true. Suppose the toggle operation is true for a string of length $k$. Let 
$\begin{bmatrix} p & q \\ r & s \end{bmatrix}$ be the transformation matrix of the string of length $k$. Adding the character $A$ will give the transformation matrix:

$$
\begin{bmatrix} p & q \\ r & s \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} = 
\begin{bmatrix} p + q & q \\ r + s & s \end{bmatrix}
$$

Applying the toggle operation on the left hand side gives us:

$$
\begin{bmatrix} s & r \\ q & p \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = 
\begin{bmatrix} s & r + s \\ q & p + q \end{bmatrix}
$$

The prove for “adding character B” can be done similarly. Hence, the toggle operation is proven to be true.

The total complexity is $\mathcal{O}(Q \log N)$.


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}