Crayons

Lets solve it assuming that there is only one friend instead of five.

We will iterate from i=1 to i=M and maintain a set S that will contain at most N elements. In this set we will keep rightmost indices of last N distinct colors. While inserting current index i in S we will have to handle two cases:

• If the previous index of the i'th color is already in S, then we will erase that from S and insert i in S. We will need a pre-computed array or map to get the previous index of i'th color in constant time.
• If any index of the i'th color is not in the set, then we will insert i in the set. If this makes the size of the set greater than N then we will erase the smallest index from S.

If after inserting i, the smallest element in S is j, then it indicates that choosing L<=j and R=i will give us at least N distinct colors and choosing L>j and R=i will give us less than N colors. Hence, we can find and store the maximum L for all R that gives us N distinct colors and answer each query in constant time.

To solve the main problem, we will have to perform the procedure described above for each of five friends.