Suppose you have a row of N cats, numbered from 0 to N - 1. Initially, all the cats are painted black. You are asked to perform Q operations of the following two types, in random order. 1.Painting Cats: Given a range a to b(inclusive), cats within the range are painted with a new color. Example input:
Type of operation | Start index | End index | Color
1 0 10 blue
No output (void)
2.Query Cat: Given a particular number a, return the color of the cat numbered a. Example input:
Type of operation | number
2 10
Example output:
blue
It is guaranteed that 1 ≤ N ≤ 1,000,000,000 and 1≤Q ≤ 300,000. Create a time and space efficient solution.
I could not answer this question without a hint given by my classmate. Not a difficult question to understand, so feel free to think of a solution if you can, before reading on.