# PROBLEM LINK:

* Author:* Naman Jain

*Anshul Asawa*

**Tester:***Naman Jain*

**Editorialist:**# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Segment-tree(Lazy propagation), matrix-multiplication

# PROBLEM:

The problem is self-explanatory.

- For a query of Type 1, you will be given two numbers L and R and a character C. You are supposed to replace every character in S from position L to R with C.
- For a query of Type 2, you will be given 4 numbers L,R, p and q. Now, for every character in S from position L to R, perform the following operations in the order left to right:
- If the character is 'A', then replace p with ( p − q + MOD ) \% MOD and q with ( p + q) \% MOD.
- If the character is 'B', then replace p with (p + q) \% MOD and q with (q − p + MOD) \% MOD.

# EXPLANATION:

Let the transformation matrix for characters ‘A’ and ‘B’ be

\begin{bmatrix}
1 & 1 \\
-1 & 1 \\
\end{bmatrix}
\quad
and
\begin{bmatrix}
1 & -1 \\
1 & 1 \\
\end{bmatrix}
\quad
respectively. This is because:

\begin{bmatrix}
a & b \\
\end{bmatrix}
\quad
\begin{bmatrix}
1 & 1 \\
-1 & 1 \\
\end{bmatrix}
\quad
=
\begin{bmatrix}
a-b & a+b \\
\end{bmatrix}
\quad

and

\begin{bmatrix}
a & b \\
\end{bmatrix}
\quad
\begin{bmatrix}
1 & -1 \\
1 & 1 \\
\end{bmatrix}
\quad
=
\begin{bmatrix}
a+b & b-a \\
\end{bmatrix}
\quad

Next, we build a segment tree of size N, where each node is a 2 × 2 matrix which is the multiplication of its two children. The i-th leaf node is
\begin{bmatrix}
1 & 1 \\
-1 & 1 \\
\end{bmatrix}
\quad
if S[i] = ‘A’ or
\begin{bmatrix}
1 & -1 \\
1 & 1 \\
\end{bmatrix}
\quad
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 p and q with this matrix will give us the answer.

To update the segment tree(with lazy propagation) we create two arrays storing the powers of each transformation matrix upto N and do the lazy update on the segment tree.

# TIME-COMPLEXITY:

O((N+Q)log(N))