PROBLEM LINK:
Author: Naman Jain
Tester: Anshul Asawa
Editorialist: Naman Jain
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))