Editorial for BSSPC '22 P8 - Bayview's RGB Gaming PC

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

Hint 1

Represent RGB as integers mod $3$ ~3~ instead of letters.

Hint 2

Calculate the difference $D = A - B$ ~D = A - B~ and operate on it instead. Our condition is now that $D$ ~D~ is all zero.

Full Solution

Yes, a segment tree will work, and yes, it will pass. However, it is not required.

Instead, use a difference array. Note that an array is all zero if and only if the difference array is all zero. We can keep track of how many zeroes we have in our difference array after each operation, as each update modifies $2$ ~2~ indices.

Comments

There are no comments at the moment.