Author: Naman Jain
Tester: Anshul Asawa
Editorialist: Naman Jain




Segment-tree(Lazy propagation), matrix-multiplication


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.


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




Setter’s Solution


Thanks for the editorial, easy to understand.

The questions using transformation matrix confuse me. It’s not obvious from the question that it could be solved using this technique. Can you tell me in what type of questions I should think this way?

Most of the time transformation matrices are used for linear equations. So whenever you see a question involving liner equation, you can try to solve the question with it.

And mostly equations are formed in questions involving DP.
Thanks @theanshul, I’ll keep this in mind.